diff --git a/src/avalanche/peermanager.cpp b/src/avalanche/peermanager.cpp
--- a/src/avalanche/peermanager.cpp
+++ b/src/avalanche/peermanager.cpp
@@ -81,6 +81,11 @@
 }
 
 bool PeerManager::removeNode(NodeId nodeid) {
+    if (pendingNodes.get<by_nodeid>().erase(nodeid) > 0) {
+        // If this was a pending node, there is nothing else to do.
+        return true;
+    }
+
     auto it = nodes.find(nodeid);
     if (it == nodes.end()) {
         return false;
@@ -89,8 +94,6 @@
     const PeerId peerid = it->peerid;
     nodes.erase(it);
 
-    pendingNodes.get<by_nodeid>().erase(nodeid);
-
     // Keep the track of the reference count.
     bool success = removeNodeFromPeer(peers.find(peerid));
     assert(success);
diff --git a/src/avalanche/test/peermanager_tests.cpp b/src/avalanche/test/peermanager_tests.cpp
--- a/src/avalanche/test/peermanager_tests.cpp
+++ b/src/avalanche/test/peermanager_tests.cpp
@@ -506,6 +506,15 @@
         BOOST_CHECK_EQUAL(pm.getPendingNodeCount(), 10);
     }
     BOOST_CHECK(pm.verify());
+
+    // Remove the remaining pending nodes, check the count drops accordingly
+    for (int i = 0; i < 10; i++) {
+        BOOST_CHECK(pm.removeNode(i));
+        BOOST_CHECK(!TestPeerManager::isNodePending(pm, i));
+        BOOST_CHECK(!TestPeerManager::nodeBelongToPeer(pm, i, peerid));
+        BOOST_CHECK_EQUAL(pm.getNodeCount(), 0);
+        BOOST_CHECK_EQUAL(pm.getPendingNodeCount(), 10 - i - 1);
+    }
 }
 
 BOOST_AUTO_TEST_CASE(node_binding_reorg) {