diff --git a/mercurial/obsolete.py b/mercurial/obsolete.py
--- a/mercurial/obsolete.py
+++ b/mercurial/obsolete.py
@@ -583,7 +583,7 @@
 
         metadata = tuple(sorted(metadata.iteritems()))
 
-        marker = (str(prec), tuple(succs), int(flag), metadata, date, parents)
+        marker = (bytes(prec), tuple(succs), int(flag), metadata, date, parents)
         return bool(self.add(transaction, [marker]))
 
     def add(self, transaction, markers):