diff --git a/src/avalanche/processor.h b/src/avalanche/processor.h
--- a/src/avalanche/processor.h
+++ b/src/avalanche/processor.h
@@ -60,6 +60,7 @@
     Rejected,
     Accepted,
     Finalized,
+    Stale,
 };
 
 template <typename VoteItem> class VoteItemUpdate {
diff --git a/src/avalanche/processor.cpp b/src/avalanche/processor.cpp
--- a/src/avalanche/processor.cpp
+++ b/src/avalanche/processor.cpp
@@ -510,6 +510,13 @@
 
             auto &vr = it->second;
             if (!vr.registerVote(nodeid, v.GetError())) {
+                if (vr.isStale()) {
+                    updates.emplace_back(item, VoteStatus::Stale);
+
+                    // Just drop stale votes. If we see this item again, we'll
+                    // do a new vote.
+                    voteRecordsWriteView->erase(it);
+                }
                 // This vote did not provide any extra information, move on.
                 continue;
             }
diff --git a/src/avalanche/test/processor_tests.cpp b/src/avalanche/test/processor_tests.cpp
--- a/src/avalanche/test/processor_tests.cpp
+++ b/src/avalanche/test/processor_tests.cpp
@@ -319,10 +319,8 @@
     CBlockIndex *pindex = &index;
 
     std::set<VoteStatus> status{
-        VoteStatus::Invalid,
-        VoteStatus::Rejected,
-        VoteStatus::Accepted,
-        VoteStatus::Finalized,
+        VoteStatus::Invalid,   VoteStatus::Rejected, VoteStatus::Accepted,
+        VoteStatus::Finalized, VoteStatus::Stale,
     };
 
     for (auto s : status) {
diff --git a/src/net_processing.cpp b/src/net_processing.cpp
--- a/src/net_processing.cpp
+++ b/src/net_processing.cpp
@@ -5026,6 +5026,9 @@
                 case avalanche::VoteStatus::Finalized:
                     voteOutcome = "finalized";
                     break;
+                case avalanche::VoteStatus::Stale:
+                    voteOutcome = "stalled";
+                    break;
 
                     // No default case, so the compiler can warn about missing
                     // cases
@@ -5045,10 +5048,14 @@
             auto nextCooldownTimePoint = GetTime<std::chrono::seconds>();
             switch (u.getStatus()) {
                 case avalanche::VoteStatus::Invalid:
-                    rejectionMode =
-                        avalanche::PeerManager::RejectionMode::INVALIDATE;
                     WITH_LOCK(cs_rejectedProofs,
                               rejectedProofs->insert(proofid));
+                    // Fallthrough
+                case avalanche::VoteStatus::Stale:
+                    // Invalidate mode removes the proof from all proof pools
+                    rejectionMode =
+                        avalanche::PeerManager::RejectionMode::INVALIDATE;
+                    // Fallthrough
                 case avalanche::VoteStatus::Rejected:
                     if (g_avalanche->withPeerManager(
                             [&](avalanche::PeerManager &pm) {
@@ -5110,6 +5117,11 @@
                         LOCK(cs_main);
                         m_chainman.ActiveChainstate().UnparkBlock(pindex);
                     } break;
+                    case avalanche::VoteStatus::Stale:
+                        // Fall back on Nakamoto consensus in the absence of
+                        // Avalanche votes for other competing or descendant
+                        // blocks.
+                        break;
                 }
             }
 
diff --git a/test/functional/abc_p2p_avalanche_proof_voting.py b/test/functional/abc_p2p_avalanche_proof_voting.py
--- a/test/functional/abc_p2p_avalanche_proof_voting.py
+++ b/test/functional/abc_p2p_avalanche_proof_voting.py
@@ -114,6 +114,7 @@
         self.poll_tests(node)
         self.update_tests(node)
         self.vote_tests(node)
+        self.stale_proof_tests(node)
 
     def poll_tests(self, node):
         proof_seq10 = self.build_conflicting_proof(node, 10)
@@ -190,7 +191,7 @@
         peer.wait_for_disconnect()
 
     def update_tests(self, node):
-        # Restart the node to get rid og in-flight requests
+        # Restart the node to get rid of in-flight requests
         self.restart_node(0)
 
         mock_time = int(time.time())
@@ -414,6 +415,56 @@
             AvalancheVote(AvalancheProofVoteResponse.CONFLICT, proof_3_id),
             AvalancheVote(AvalancheProofVoteResponse.REJECTED, proof_4_id)])
 
+    def stale_proof_tests(self, node):
+        # Restart the node to get rid of in-flight requests
+        self.restart_node(0)
+
+        mock_time = int(time.time())
+        node.setmocktime(mock_time)
+
+        self.quorum = self.get_quorum(node)
+        peer = get_ava_p2p_interface(node)
+
+        proof_seq1 = self.build_conflicting_proof(node, 1)
+        proof_seq2 = self.build_conflicting_proof(node, 2)
+        proofid_seq1 = avalanche_proof_from_hex(proof_seq1).proofid
+        proofid_seq2 = avalanche_proof_from_hex(proof_seq2).proofid
+
+        node.sendavalancheproof(proof_seq2)
+        self.wait_until(lambda: proofid_seq2 in get_proof_ids(node))
+
+        assert proofid_seq2 in get_proof_ids(node)
+        assert proofid_seq1 not in get_proof_ids(node)
+
+        mock_time += self.conflicting_proof_cooldown
+        node.setmocktime(mock_time)
+
+        peer.send_avaproof(avalanche_proof_from_hex(proof_seq1))
+
+        # Wait until proof_seq1 voting goes stale
+        retry = 5
+        while retry > 0:
+            try:
+                with node.assert_debug_log([f"Avalanche stalled proof {proofid_seq1:0{64}x}"]):
+                    self.wait_until(lambda: not self.can_find_proof_in_poll(
+                        proofid_seq1, response=AvalancheProofVoteResponse.UNKNOWN), timeout=30)
+                break
+            except AssertionError:
+                retry -= 1
+
+        assert_greater_than(retry, 0)
+
+        # Verify that proof_seq2 was not replaced
+        assert proofid_seq2 in get_proof_ids(node)
+        assert proofid_seq1 not in get_proof_ids(node)
+
+        # When polled, peer responds with expected votes for both proofs
+        peer.send_poll([proofid_seq1, proofid_seq2], MSG_AVA_PROOF)
+        response = peer.wait_for_avaresponse()
+        assert repr(response.response.votes) == repr([
+            AvalancheVote(AvalancheProofVoteResponse.UNKNOWN, proofid_seq1),
+            AvalancheVote(AvalancheProofVoteResponse.ACTIVE, proofid_seq2)])
+
 
 if __name__ == '__main__':
     AvalancheProofVotingTest().main()