--- a/mercurial/tags.py	Wed May 16 11:40:33 2012 -0500
+++ b/mercurial/tags.py	Sun May 13 12:01:52 2012 +0200
@@ -228,6 +228,11 @@
 
     # N.B. in case 4 (nodes destroyed), "new head" really means "newly
     # exposed".
+    if not len(repo.file('.hgtags')):
+        # No tags have ever been committed, so we can avoid a
+        # potentially expensive search.
+        return (repoheads, cachefnode, None, True)
+
     newheads = [head
                 for head in repoheads
                 if head not in set(cacheheads)]