diff --git a/src/avalanche/peermanager.cpp b/src/avalanche/peermanager.cpp
--- a/src/avalanche/peermanager.cpp
+++ b/src/avalanche/peermanager.cpp
@@ -85,7 +85,13 @@
 
 bool PeerManager::removeNodeFromPeer(const PeerSet::iterator &it,
                                      uint32_t count) {
-    assert(it != peers.end());
+    // It is possible for nodes to be dangling. If there was an inflight query
+    // when the peer gets removed, the node was not erased. In this case there
+    // is nothing to do.
+    if (it == peers.end()) {
+        return true;
+    }
+
     assert(count <= it->node_count);
     if (count == 0) {
         // This is a NOOP.
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
@@ -554,4 +554,49 @@
     BOOST_CHECK(isGoodPeer(proof2));
 }
 
+BOOST_AUTO_TEST_CASE(dangling_node) {
+    avalanche::PeerManager pm;
+
+    auto proof = getRandomProofPtr(MIN_VALID_PROOF_SCORE);
+    PeerId peerid = pm.getPeerId(proof);
+    BOOST_CHECK_NE(peerid, NO_PEER);
+
+    const TimePoint theFuture(std::chrono::steady_clock::now() +
+                              std::chrono::hours(24));
+
+    // Add nodes to this peer and update their request time far in the future
+    for (int i = 0; i < 10; i++) {
+        BOOST_CHECK(pm.addNode(i, proof->getId()));
+        BOOST_CHECK(pm.updateNextRequestTime(i, theFuture));
+    }
+
+    // Remove the peer
+    BOOST_CHECK(pm.removePeer(peerid));
+
+    // Check the nodes are still there
+    for (int i = 0; i < 10; i++) {
+        BOOST_CHECK(pm.forNode(i, [](const Node &n) { return true; }));
+    }
+
+    // Build a new one
+    proof = getRandomProofPtr(MIN_VALID_PROOF_SCORE);
+    peerid = pm.getPeerId(proof);
+    BOOST_CHECK_NE(peerid, NO_PEER);
+
+    // Update the nodes with the new proof
+    for (int i = 0; i < 10; i++) {
+        BOOST_CHECK(pm.addNode(i, proof->getId()));
+        BOOST_CHECK(pm.forNode(
+            i, [&](const Node &n) { return n.nextRequestTime == theFuture; }));
+    }
+
+    // Remove the peer
+    BOOST_CHECK(pm.removePeer(peerid));
+
+    // Disconnect the nodes
+    for (int i = 0; i < 10; i++) {
+        BOOST_CHECK(pm.removeNode(i));
+    }
+}
+
 BOOST_AUTO_TEST_SUITE_END()