diff --git a/mercurial/verify.py b/mercurial/verify.py
--- a/mercurial/verify.py
+++ b/mercurial/verify.py
@@ -219,6 +219,7 @@ def _verify(repo):
         elif size > 0 or not revlogv1:
             storefiles.add(_normpath(f))
 
+    fncachewarned = False
     files = sorted(set(filenodes) | set(filelinkrevs))
     total = len(files)
     for i, f in enumerate(files):
@@ -245,6 +246,7 @@ def _verify(repo):
                 storefiles.remove(ff)
             except KeyError:
                 warn(_(" warning: revlog '%s' not in fncache!") % ff)
+                fncachewarned = True
 
         checklog(fl, f, lr)
         seen = {}
@@ -313,6 +315,9 @@ def _verify(repo):
                    (len(files), len(cl), revisions))
     if warnings[0]:
         ui.warn(_("%d warnings encountered!\n") % warnings[0])
+    if fncachewarned:
+        ui.warn(_('hint: run "hg debugrebuildfncache" to recover from '
+                  'corrupt fncache\n'))
     if errors[0]:
         ui.warn(_("%d integrity errors encountered!\n") % errors[0])
         if badrevs:
diff --git a/tests/test-fncache.t b/tests/test-fncache.t
--- a/tests/test-fncache.t
+++ b/tests/test-fncache.t
@@ -53,6 +53,23 @@ Testing verify:
    warning: revlog 'data/a.i/b.i' not in fncache!
   3 files, 3 changesets, 3 total revisions
   3 warnings encountered!
+  hint: run "hg debugrebuildfncache" to recover from corrupt fncache
+
+Follow the hint to make sure it works
+
+  $ hg debugrebuildfncache
+  adding data/a.i
+  adding data/a.i.hg/c.i
+  adding data/a.i/b.i
+  3 items added, 0 removed from fncache
+
+  $ hg verify
+  checking changesets
+  checking manifests
+  crosschecking files in changesets and manifests
+  checking files
+  3 files, 3 changesets, 3 total revisions
+
   $ cd ..
 
 Non store repo:
diff --git a/tests/test-verify.t b/tests/test-verify.t
--- a/tests/test-verify.t
+++ b/tests/test-verify.t
@@ -55,6 +55,7 @@ introduce some bugs in repo
    bar.txt@0: 256559129457 in manifests not found
   3 files, 1 changesets, 0 total revisions
   3 warnings encountered!
+  hint: run "hg debugrebuildfncache" to recover from corrupt fncache
   6 integrity errors encountered!
   (first damaged changeset appears to be 0)
   [1]