diff --git a/src/avalanche/peermanager.cpp b/src/avalanche/peermanager.cpp
--- a/src/avalanche/peermanager.cpp
+++ b/src/avalanche/peermanager.cpp
@@ -40,9 +40,14 @@
             return false;
         }
 
-        // We actually have this node already, we need to update it.
-        bool success = removeNodeFromPeer(peers.find(oldpeerid));
-        assert(success);
+        // It is possible for the node to be dangling. If there was an inflight
+        // query when the peer gets removed, the node was not erased.
+        auto oldpeer_it = peers.find(oldpeerid);
+        if (oldpeer_it != peers.end()) {
+            // We actually have this node already, we need to update it.
+            bool success = removeNodeFromPeer(oldpeer_it);
+            assert(success);
+        }
     }
 
     bool success = addNodeToPeer(it);
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,36 @@
     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));
+
+    // 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; }));
+    }
+}
+
 BOOST_AUTO_TEST_SUITE_END()