diff --git a/mercurial/tags.py b/mercurial/tags.py
--- a/mercurial/tags.py
+++ b/mercurial/tags.py
@@ -494,11 +494,25 @@
     starttime = util.timer()
     fnodescache = hgtagsfnodescache(repo.unfiltered())
     cachefnode = {}
+    validatedfnodes = set()
+    unknownentries = set()
     for node in nodes:
         fnode = fnodescache.getfnode(node)
         if fnode != nullid:
+            if fnode not in validatedfnodes:
+                try:
+                    repo.filectx(b'.hgtags', fileid=fnode).data()
+                    validatedfnodes.add(fnode)
+                except error.LookupError:
+                    unknownentries.add(node)
             cachefnode[node] = fnode
 
+    if unknownentries:
+        fixednodemap = fnodescache.recomputefnodes(unknownentries)
+        for node, fnode in pycompat.iteritems(fixednodemap):
+            if fnode != nullid:
+                cachefnode[node] = fnode
+
     fnodescache.write()
 
     duration = util.timer() - starttime
@@ -826,6 +840,16 @@
 
         self._writeentry(ctx.rev() * _fnodesrecsize, node[0:4], fnode)
 
+    def recomputefnodes(self, nodes):
+        """recomputes file nodes for given nodes as the current ones are
+        unknown and return a map of node -> recomputed fnode"""
+        fixednodemap = {}
+        for node in nodes:
+            fnode = self._computefnode(node)
+            fixednodemap[node] = fnode
+            self.setfnode(node, fnode)
+        return fixednodemap
+
     def _writeentry(self, offset, prefix, fnode):
         # Slices on array instances only accept other array.
         entry = bytearray(prefix + fnode)
diff --git a/tests/test-tags.t b/tests/test-tags.t
--- a/tests/test-tags.t
+++ b/tests/test-tags.t
@@ -452,8 +452,8 @@
   5 8dbfe60eff306a54259cfe007db9e330e7ecf866 0c04f2a8deadde17fab7422878ee5a2dadbc943d (unknown node)
 
   $ hg tags
-  abort: data/.hgtags.i@0c04f2a8deadde17fab7422878ee5a2dadbc943d: no match found
-  [50]
+  tip                                5:8dbfe60eff30
+  bar                                1:78391a272241
 
 BUG: Unless this file is restored, the `hg tags` in the next unix-permissions
 conditional will fail: "abort: data/.hgtags.i@0c04f2a8dead: no match found"