diff --git a/src/main/java/com/googlesource/gerrit/plugins/validation/dfsrefdb/zookeeper/ZkSharedRefDatabase.java b/src/main/java/com/googlesource/gerrit/plugins/validation/dfsrefdb/zookeeper/ZkSharedRefDatabase.java
index 01d19f2..04dc067 100644
--- a/src/main/java/com/googlesource/gerrit/plugins/validation/dfsrefdb/zookeeper/ZkSharedRefDatabase.java
+++ b/src/main/java/com/googlesource/gerrit/plugins/validation/dfsrefdb/zookeeper/ZkSharedRefDatabase.java
@@ -117,7 +117,8 @@
         new DistributedAtomicValue(client, pathFor(projectName, oldRef), retryPolicy);
 
     try {
-      if (oldRef.getObjectId() == null || oldRef.getObjectId().equals(ObjectId.zeroId())) {
+      if ((oldRef.getObjectId() == null || oldRef.getObjectId().equals(ObjectId.zeroId()))
+          && refNotInZk(projectName, oldRef)) {
         return distributedRefValue.initialize(writeObjectId(newRefValue));
       }
       final ObjectId newValue = newRefValue == null ? ObjectId.zeroId() : newRefValue;
diff --git a/src/test/java/com/googlesource/gerrit/plugins/validation/dfsrefdb/zookeeper/ZkSharedRefDatabaseTest.java b/src/test/java/com/googlesource/gerrit/plugins/validation/dfsrefdb/zookeeper/ZkSharedRefDatabaseTest.java
index fd7b3c0..3ee4612 100644
--- a/src/test/java/com/googlesource/gerrit/plugins/validation/dfsrefdb/zookeeper/ZkSharedRefDatabaseTest.java
+++ b/src/test/java/com/googlesource/gerrit/plugins/validation/dfsrefdb/zookeeper/ZkSharedRefDatabaseTest.java
@@ -92,6 +92,19 @@
   }
 
   @Test
+  public void shouldCompareAndPutPreviouslyRemovedRefSuccessfully() throws Exception {
+    Ref ref = refOf(AN_OBJECT_ID_1);
+    Project.NameKey projectName = A_TEST_PROJECT_NAME_KEY;
+
+    zookeeperContainer.createRefInZk(projectName, ref);
+
+    assertThat(zkSharedRefDatabase.compareAndPut(projectName, ref, ObjectId.zeroId())).isTrue();
+
+    Ref zerosRef = refOf(ObjectId.zeroId());
+    assertThat(zkSharedRefDatabase.compareAndPut(projectName, zerosRef, AN_OBJECT_ID_1)).isTrue();
+  }
+
+  @Test
   public void compareAndPutShouldFailIfTheObjectionHasNotTheExpectedValue() throws Exception {
     Project.NameKey projectName = A_TEST_PROJECT_NAME_KEY;