diff --git a/mercurial/util.py b/mercurial/util.py
--- a/mercurial/util.py
+++ b/mercurial/util.py
@@ -1341,6 +1341,28 @@
 
         return result
 
+    def popoldest(self):
+        """Remove the oldest item from the cache.
+
+        Returns the (key, value) describing the removed cache entry.
+        """
+        if not self._cache:
+            return
+
+        # Walk the linked list backwards starting at tail node until we hit
+        # a non-empty node.
+        n = self._head.prev
+        while n.key is _notset:
+            n = n.prev
+
+        key, value = n.key, n.value
+
+        # And remove it from the cache and mark it as empty.
+        del self._cache[n.key]
+        n.markempty()
+
+        return key, value
+
     def _movetohead(self, node):
         """Mark a node as the newest, making it the new head.
 
diff --git a/tests/test-lrucachedict.py b/tests/test-lrucachedict.py
--- a/tests/test-lrucachedict.py
+++ b/tests/test-lrucachedict.py
@@ -172,5 +172,30 @@
             self.assertIn(key, d)
             self.assertEqual(d[key], 'v%s' % key)
 
+    def testpopoldest(self):
+        d = util.lrucachedict(4)
+        d['a'] = 'va'
+        d['b'] = 'vb'
+
+        self.assertEqual(len(d), 2)
+        self.assertEqual(d.popoldest(), ('a', 'va'))
+        self.assertEqual(len(d), 1)
+        self.assertEqual(d.popoldest(), ('b', 'vb'))
+        self.assertEqual(len(d), 0)
+        self.assertIsNone(d.popoldest())
+
+        d['a'] = 'va'
+        d['b'] = 'vb'
+        d['c'] = 'vc'
+        d['d'] = 'vd'
+
+        self.assertEqual(d.popoldest(), ('a', 'va'))
+        self.assertEqual(len(d), 3)
+        for key in ('b', 'c', 'd'):
+            self.assertEqual(d[key], 'v%s' % key)
+
+        d['a'] = 'va'
+        self.assertEqual(d.popoldest(), ('b', 'vb'))
+
 if __name__ == '__main__':
     silenttestrunner.main(__name__)