diff --git a/hgext/remotefilelog/__init__.py b/hgext/remotefilelog/__init__.py
--- a/hgext/remotefilelog/__init__.py
+++ b/hgext/remotefilelog/__init__.py
@@ -478,9 +478,10 @@
     def findrenames(orig, repo, matcher, added, removed, *args, **kwargs):
         if isenabled(repo):
             files = []
-            parentctx = repo['.']
+            pmf = repo['.'].manifest()
             for f in removed:
-                files.append((f, hex(parentctx.filenode(f))))
+                if f in pmf:
+                    files.append((f, hex(pmf[f])))
             # batch fetch the needed files from the server
             repo.fileservice.prefetch(files)
         return orig(repo, matcher, added, removed, *args, **kwargs)
diff --git a/tests/test-remotefilelog-prefetch.t b/tests/test-remotefilelog-prefetch.t
--- a/tests/test-remotefilelog-prefetch.t
+++ b/tests/test-remotefilelog-prefetch.t
@@ -197,6 +197,9 @@
   $ mv x x2
   $ mv y y2
   $ mv z z2
+  $ echo a > a
+  $ hg add a
+  $ rm a
   $ clearcache
   $ hg addremove -s 50 > /dev/null
   3 files fetched over 1 fetches - (3 misses, 0.00% hit ratio) over * (glob)