diff --git a/mercurial/tags.py b/mercurial/tags.py
--- a/mercurial/tags.py
+++ b/mercurial/tags.py
@@ -201,6 +201,18 @@
         ), b"tag cache returned bogus head %s" % short(head)
     fnodes = _filterfnodes(tagfnode, reversed(heads))
     alltags, invalidnodes = _tagsfromfnodes(ui, repo, fnodes)
+    recomputeheads = []
+    for head, fnode in pycompat.iteritems(tagfnode):
+        if fnode in invalidnodes:
+            recomputeheads.append(head)
+    # only hgtagsfnodes contains fnodes explicitly
+    if source == 'hgtagsfnodes' and recomputeheads:
+        ui.debug(
+            b'found invalid fnodes for "%s", updating them\n'
+            % b','.join([hex(h) for h in recomputeheads])
+        )
+        fnodescache = hgtagsfnodescache(repo.unfiltered())
+        fnodescache.recomputefnodes(recomputeheads)
 
     # and update the cache (if necessary)
     if shouldwrite:
@@ -795,6 +807,14 @@
         self._writeentry(offset, properprefix, fnode)
         return fnode
 
+    def recomputefnodes(self, nodes):
+        """recomputes file nodes for given nodes as the current ones are
+        invalid and write the updates to the cache"""
+        for node in nodes:
+            fnode = self._computefnode(node)
+            self.setfnode(node, fnode)
+        self.write()
+
     def _computefnode(self, node):
         """Finds the tag filenode for a node which is missing or invalid
         in cache"""
diff --git a/tests/test-tags.t b/tests/test-tags.t
--- a/tests/test-tags.t
+++ b/tests/test-tags.t
@@ -451,9 +451,17 @@
   4 0c192d7d5e6b78a714de54a2e9627952a877e25a 0c04f2a8af31de17fab7422878ee5a2dadbc943d
   5 8dbfe60eff306a54259cfe007db9e330e7ecf866 0c04f2a8deadde17fab7422878ee5a2dadbc943d (invalid node)
 
-  $ hg tags
-  tip                                5:8dbfe60eff30
-  bar                                1:78391a272241
+  $ hg tags --debug
+  found invalid fnodes for "8dbfe60eff306a54259cfe007db9e330e7ecf866", updating them
+  tip                                5:8dbfe60eff306a54259cfe007db9e330e7ecf866
+  bar                                1:78391a272241d70354aa14c874552cad6b51bb42
+
+  $ hg debugtagscache | tail -2
+  4 0c192d7d5e6b78a714de54a2e9627952a877e25a 0c04f2a8af31de17fab7422878ee5a2dadbc943d
+  5 8dbfe60eff306a54259cfe007db9e330e7ecf866 0c04f2a8af31de17fab7422878ee5a2dadbc943d
+  $ hg tags --debug
+  tip                                5:8dbfe60eff306a54259cfe007db9e330e7ecf866
+  bar                                1:78391a272241d70354aa14c874552cad6b51bb42
 
 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"