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