diff --git a/mercurial/bookmarks.py b/mercurial/bookmarks.py
--- a/mercurial/bookmarks.py
+++ b/mercurial/bookmarks.py
@@ -173,6 +173,8 @@ class bmstore(object):
             nrefs.sort()
 
     def _del(self, mark):
+        if mark not in self._refmap:
+            return
         self._clean = False
         node = self._refmap.pop(mark)
         nrefs = self._nodemap[node]
diff --git a/relnotes/next b/relnotes/next
--- a/relnotes/next
+++ b/relnotes/next
@@ -27,6 +27,7 @@
 
 == Bug Fixes  ==
 
+ * Fix server exception when concurrent pushes delete the same bookmark
 
 == Backwards Compatibility Changes ==