diff --git a/hgext/remotenames.py b/hgext/remotenames.py
--- a/hgext/remotenames.py
+++ b/hgext/remotenames.py
@@ -10,6 +10,11 @@
 
 from __future__ import absolute_import
 
+import UserDict
+
+from mercurial.node import (
+    bin,
+)
 from mercurial import (
     logexchange,
 )
@@ -20,34 +25,102 @@
 # leave the attribute unspecified.
 testedwith = 'ships-with-hg-core'
 
+class lazyremotenamedict(UserDict.DictMixin):
+    """
+    Read-only dict-like Class to lazily resolve remotename entries
+
+    We are doing that because remotenames startup was slow.
+    We lazily read the remotenames file once to figure out the potential entries
+    and store them in self.potentialentries. Then when asked to resolve an
+    entry, if it is not in self.potentialentries, then it isn't there, if it
+    is in self.potentialentries we resolve it and store the result in
+    self.cache. We cannot be lazy is when asked all the entries (keys).
+    """
+    def __init__(self, kind, repo):
+        self.cache = {}
+        self.potentialentries = {}
+        self._kind = kind # bookmarks or branches
+        self._repo = repo
+        self.loaded = False
+
+    def _load(self):
+        """ Read the remotenames file, store entries matching selected kind """
+        self.loaded = True
+        repo = self._repo
+        for node, rpath, rname in logexchange.readremotenamefile(repo,
+                                                                self._kind):
+            name = rpath + '/' + rname
+            self.potentialentries[name] = (node, rpath, name)
+
+    def _resolvedata(self, potentialentry):
+        """ Check that the node for potentialentry exists and return it """
+        if not potentialentry in self.potentialentries:
+            return None
+        node, remote, name = self.potentialentries[potentialentry]
+        repo = self._repo
+        binnode = bin(node)
+        # if the node doesn't exist, skip it
+        try:
+            repo.changelog.rev(binnode)
+        except LookupError:
+            return None
+        # Skip closed branches
+        if (self._kind == 'branches' and repo[binnode].closesbranch()):
+            return None
+        return [binnode]
+
+    def __getitem__(self, key):
+        if not self.loaded:
+            self._load()
+        val = self._fetchandcache(key)
+        if val is not None:
+            return val
+        else:
+            raise KeyError()
+
+    def _fetchandcache(self, key):
+        if key in self.cache:
+            return self.cache[key]
+        val = self._resolvedata(key)
+        if val is not None:
+            self.cache[key] = val
+            return val
+        else:
+            return None
+
+    def keys(self):
+        """ Get a list of bookmark or branch names """
+        if not self.loaded:
+            self._load()
+        return self.potentialentries.keys()
+
+    def iteritems(self):
+        """ Iterate over (name, node) tuples """
+
+        if not self.loaded:
+            self._load()
+
+        for k, vtup in self.potentialentries.iteritems():
+            yield (k, [bin(vtup[0])])
+
 class remotenames(dict):
     """
     This class encapsulates all the remotenames state. It also contains
-    methods to access that state in convenient ways.
+    methods to access that state in convenient ways. Remotenames are lazy
+    loaded. Whenever client code needs to ensure the freshest copy of
+    remotenames, use the `clearnames` method to force an eventual load.
     """
 
     def __init__(self, repo, *args):
         dict.__init__(self, *args)
         self._repo = repo
-        self['bookmarks'] = {}
-        self['branches'] = {}
-        self.loadnames()
-        self._loadednames = True
-
-    def loadnames(self):
-        """ loads the remotenames information from the remotenames file """
-        for rtype in ('bookmarks', 'branches'):
-            for node, rpath, name in logexchange.readremotenamefile(self._repo,
-                                                                    rtype):
-                rname = rpath + '/' + name
-                self[rtype][rname] = [node]
+        self.clearnames()
 
     def clearnames(self):
         """ Clear all remote names state """
-        self['bookmarks'] = {}
-        self['branches'] = {}
+        self['bookmarks'] = lazyremotenamedict("bookmarks", self._repo)
+        self['branches'] = lazyremotenamedict("branches", self._repo)
         self._invalidatecache()
-        self._loadednames = False
 
     def _invalidatecache(self):
         self._nodetobmarks = None