diff --git a/hgext/largefiles/basestore.py b/hgext/largefiles/basestore.py
--- a/hgext/largefiles/basestore.py
+++ b/hgext/largefiles/basestore.py
@@ -48,8 +48,8 @@ class basestore(object):
         '''Put source file into the store under <filename>/<hash>.'''
         raise NotImplementedError('abstract method')
 
-    def exists(self, hash):
-        '''Check to see if the store contains the given hash.'''
+    def exists(self, hashes):
+        '''Check to see if the store contains the given hashes.'''
         raise NotImplementedError('abstract method')
 
     def get(self, files):
diff --git a/hgext/largefiles/lfcommands.py b/hgext/largefiles/lfcommands.py
--- a/hgext/largefiles/lfcommands.py
+++ b/hgext/largefiles/lfcommands.py
@@ -340,7 +340,11 @@ def uploadlfiles(ui, rsrc, rdst, files):
     store = basestore._openstore(rsrc, rdst, put=True)
 
     at = 0
-    files = filter(lambda h: not store.exists(h), files)
+    ui.debug("sending statlfile command for %d largefiles\n" % len(files))
+    retval = store.exists(files)
+    files = filter(lambda h: not retval[h], files)
+    ui.debug("%d largefiles need to be uploaded\n" % len(files))
+
     for hash in files:
         ui.progress(_('uploading largefiles'), at, unit='largefile',
                     total=len(files))
diff --git a/hgext/largefiles/proto.py b/hgext/largefiles/proto.py
--- a/hgext/largefiles/proto.py
+++ b/hgext/largefiles/proto.py
@@ -7,6 +7,7 @@ import os
 import urllib2
 
 from mercurial import error, httprepo, util, wireproto
+from mercurial.wireproto import batchable, future
 from mercurial.i18n import _
 
 import lfutil
@@ -119,15 +120,19 @@ def wirereposetup(ui, repo):
                                                 length))
             return (length, stream)
 
+        @batchable
         def statlfile(self, sha):
+            f = future()
+            result = {'sha': sha}
+            yield result, f
             try:
-                return int(self._call("statlfile", sha=sha))
+                yield int(f.value)
             except (ValueError, urllib2.HTTPError):
                 # If the server returns anything but an integer followed by a
                 # newline, newline, it's not speaking our language; if we get
                 # an HTTP error, we can't be sure the largefile is present;
                 # either way, consider it missing.
-                return 2
+                yield 2
 
     repo.__class__ = lfileswirerepository
 
diff --git a/hgext/largefiles/remotestore.py b/hgext/largefiles/remotestore.py
--- a/hgext/largefiles/remotestore.py
+++ b/hgext/largefiles/remotestore.py
@@ -10,6 +10,7 @@ import urllib2
 
 from mercurial import util
 from mercurial.i18n import _
+from mercurial.wireproto import remotebatch
 
 import lfutil
 import basestore
@@ -20,8 +21,6 @@ class remotestore(basestore.basestore):
         super(remotestore, self).__init__(ui, repo, url)
 
     def put(self, source, hash):
-        if self._verify(hash):
-            return
         if self.sendfile(source, hash):
             raise util.Abort(
                 _('remotestore: could not put %s to remote store %s')
@@ -29,8 +28,8 @@ class remotestore(basestore.basestore):
         self.ui.debug(
             _('remotestore: put %s to remote store %s') % (source, self.url))
 
-    def exists(self, hash):
-        return self._verify(hash)
+    def exists(self, hashes):
+        return self._verify(hashes)
 
     def sendfile(self, filename, hash):
         self.ui.debug('remotestore: sendfile(%s, %s)\n' % (filename, hash))
@@ -74,8 +73,8 @@ class remotestore(basestore.basestore):
             infile = lfutil.limitreader(infile, length)
         return lfutil.copyandhash(lfutil.blockstream(infile), tmpfile)
 
-    def _verify(self, hash):
-        return not self._stat(hash)
+    def _verify(self, hashes):
+        return self._stat(hashes)
 
     def _verifyfile(self, cctx, cset, contents, standin, verified):
         filename = lfutil.splitstandin(standin)
@@ -104,3 +103,8 @@ class remotestore(basestore.basestore):
         else:
             raise RuntimeError('verify failed: unexpected response from '
                                'statlfile (%r)' % stat)
+
+    def batch(self):
+        '''Support for remote batching.'''
+        return remotebatch(self)
+
diff --git a/hgext/largefiles/wirestore.py b/hgext/largefiles/wirestore.py
--- a/hgext/largefiles/wirestore.py
+++ b/hgext/largefiles/wirestore.py
@@ -25,5 +25,13 @@ class wirestore(remotestore.remotestore)
     def _get(self, hash):
         return self.remote.getlfile(hash)
 
-    def _stat(self, hash):
-        return self.remote.statlfile(hash)
+    def _stat(self, hashes):
+        batch = self.remote.batch()
+        futures = {}
+        for hash in hashes:
+            futures[hash] = batch.statlfile(hash)
+        batch.submit()
+        retval = {}
+        for hash in hashes:
+            retval[hash] = not futures[hash].value
+        return retval