diff --git a/src/avalanche/peermanager.h b/src/avalanche/peermanager.h
--- a/src/avalanche/peermanager.h
+++ b/src/avalanche/peermanager.h
@@ -32,6 +32,11 @@
 
 namespace avalanche {
 
+/**
+ * Maximum number of valid proofs the peer manager can have registered.
+ */
+const constexpr uint32_t AVALANCHE_MAX_VALID_PROOFS = 4000;
+
 class Delegation;
 
 namespace {
@@ -123,6 +128,7 @@
     CONFLICTING,
     REJECTED,
     COOLDOWN_NOT_ELAPSED,
+    SCORE_TOO_LOW,
 };
 
 class ProofRegistrationState : public ValidationState<ProofRegistrationResult> {
@@ -369,6 +375,9 @@
     template <typename ProofContainer>
     void moveToConflictingPool(const ProofContainer &proofs);
 
+    template <typename Callable>
+    void forEachConflictingProof(const ProofRef &proof, Callable &&func);
+
     bool addOrUpdateNode(const PeerSet::iterator &it, NodeId nodeid);
     bool addNodeToPeer(const PeerSet::iterator &it);
     bool removeNodeFromPeer(const PeerSet::iterator &it, uint32_t count = 1);
diff --git a/src/avalanche/peermanager.cpp b/src/avalanche/peermanager.cpp
--- a/src/avalanche/peermanager.cpp
+++ b/src/avalanche/peermanager.cpp
@@ -188,6 +188,20 @@
     }
 }
 
+template <typename Callable>
+void PeerManager::forEachConflictingProof(const ProofRef &proof,
+                                          Callable &&func) {
+    for (const SignedStake &ss : proof->getStakes()) {
+        const ProofRef conflictingProof =
+            conflictingProofPool.getProof(ss.getStake().getUTXO());
+        if (!conflictingProof) {
+            continue;
+        }
+
+        func(conflictingProof);
+    }
+}
+
 bool PeerManager::registerProof(const ProofRef &proof,
                                 ProofRegistrationState &registrationState,
                                 RegistrationMode mode) {
@@ -225,6 +239,17 @@
         return invalidate(ProofRegistrationResult::INVALID, "invalid-proof");
     }
 
+    // If we're at the valid proof limit, only attempt to register proofs that
+    // score better or equal to the lowest scoring proof.
+    ProofRef lowestScoringProof;
+    if (validProofPool.countProofs() >= AVALANCHE_MAX_VALID_PROOFS) {
+        lowestScoringProof = validProofPool.getLowestScoreProof();
+        if (proof->getScore() < lowestScoringProof->getScore()) {
+            return invalidate(ProofRegistrationResult::SCORE_TOO_LOW,
+                              "score-too-low");
+        }
+    }
+
     auto now = GetTime<std::chrono::seconds>();
     auto nextCooldownTimePoint =
         now + std::chrono::seconds(
@@ -297,6 +322,23 @@
             return invalidate(ProofRegistrationResult::ALREADY_REGISTERED,
                               "proof-already-registered");
         case ProofPool::AddProofStatus::SUCCEED:
+            // If we're at the valid proof limit, kick out the lowest scoring
+            // proof. The new proof replaces it.
+            if (lowestScoringProof != nullptr) {
+                // First ensure any conflicting proofs are removed so they are
+                // not pulled back into the valid pool once the lowest scoring
+                // proof is removed.
+                forEachConflictingProof(lowestScoringProof,
+                                        [&](const ProofRef &conflictingProof) {
+                                            conflictingProofPool.removeProof(
+                                                conflictingProof->getId());
+                                        });
+
+                // Now remove the lowest scoring proof, making room for the new
+                // proof that was recently registered successfully.
+                rejectProof(lowestScoringProof->getId(),
+                            RejectionMode::INVALIDATE);
+            }
             break;
 
             // No default case, so the compiler can warn about missing cases
@@ -370,16 +412,10 @@
     }
 
     // If there was conflicting proofs, attempt to pull them back
-    for (const SignedStake &ss : proof->getStakes()) {
-        const ProofRef conflictingProof =
-            conflictingProofPool.getProof(ss.getStake().getUTXO());
-        if (!conflictingProof) {
-            continue;
-        }
-
+    forEachConflictingProof(proof, [&](const ProofRef &conflictingProof) {
         conflictingProofPool.removeProof(conflictingProof->getId());
         registerProof(conflictingProof);
-    }
+    });
 
     if (mode == RejectionMode::DEFAULT) {
         conflictingProofPool.addProofIfPreferred(proof);
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
@@ -1741,4 +1741,67 @@
     gArgs.ClearForcedArg("-enableavalancheproofreplacement");
 }
 
+BOOST_FIXTURE_TEST_CASE(proof_pool_limits, NoCoolDownFixture) {
+    avalanche::PeerManager pm;
+    gArgs.ForceSetArg("-enableavalancheproofreplacement", "1");
+
+    const CKey key = CKey::MakeCompressedKey();
+    std::vector<ProofRef> proofs;
+    proofs.reserve(AVALANCHE_MAX_VALID_PROOFS);
+
+    // Fill valid pool
+    for (uint32_t i = 0; i < AVALANCHE_MAX_VALID_PROOFS; i++) {
+        auto proof = buildRandomProof(MIN_VALID_PROOF_SCORE + i * 2 + 1);
+        proofs.push_back(proof);
+        BOOST_CHECK(pm.registerProof(proof));
+    }
+
+    // A proof will not be registered if its score is lower than all others in a
+    // capped out pool
+    {
+        auto proof = buildRandomProof(MIN_VALID_PROOF_SCORE);
+        ProofRegistrationState state;
+        BOOST_CHECK(!pm.registerProof(proof, state));
+        BOOST_CHECK(state.GetResult() ==
+                    ProofRegistrationResult::SCORE_TOO_LOW);
+    }
+
+    const Amount nextLowestStake =
+        int64_t(MIN_VALID_PROOF_SCORE + 2) * COIN / 100;
+    const COutPoint conflictingOutpoint = createUtxo(key, nextLowestStake);
+    auto proofSeq10 = buildProofWithOutpoints(key, {conflictingOutpoint},
+                                              nextLowestStake, key, 10);
+    auto proofSeq20 = buildProofWithOutpoints(key, {conflictingOutpoint},
+                                              nextLowestStake, key, 20);
+    auto proofSeq30 = buildProofWithOutpoints(key, {conflictingOutpoint},
+                                              nextLowestStake, key, 30);
+
+    // Register a new proof, kicking out the lowest scoring proof
+    BOOST_CHECK(proofSeq20->getStakedAmount() > proofs[0]->getStakedAmount());
+    BOOST_CHECK(pm.registerProof(proofSeq20));
+    BOOST_CHECK(!pm.isBoundToPeer(proofs[0]->getId()));
+
+    // Conflicting pool still accepts proofs
+    BOOST_CHECK(!pm.registerProof(proofSeq10));
+    BOOST_CHECK(pm.isBoundToPeer(proofSeq20->getId()));
+    BOOST_CHECK(pm.isInConflictingPool(proofSeq10->getId()));
+
+    // Preferred proof still replaces
+    BOOST_CHECK(pm.registerProof(proofSeq30));
+    BOOST_CHECK(!pm.isBoundToPeer(proofSeq20->getId()));
+
+    // Kick out the valid proof and verify the conflicting proof goes with it
+    BOOST_CHECK(pm.isInConflictingPool(proofSeq20->getId()));
+    {
+        auto proof = buildRandomProof(MIN_VALID_PROOF_SCORE + 3);
+        BOOST_CHECK(pm.registerProof(proof));
+    }
+    BOOST_CHECK(!pm.isBoundToPeer(proofSeq20->getId()));
+    BOOST_CHECK(!pm.isBoundToPeer(proofSeq30->getId()));
+    BOOST_CHECK(!pm.isInConflictingPool(proofSeq20->getId()));
+    BOOST_CHECK(!pm.isInConflictingPool(proofSeq30->getId()));
+
+    gArgs.ClearForcedArg("-enableavalancheproofreplacement");
+}
+
 BOOST_AUTO_TEST_SUITE_END()