diff --git a/src/avalanche/proofpool.h b/src/avalanche/proofpool.h
--- a/src/avalanche/proofpool.h
+++ b/src/avalanche/proofpool.h
@@ -64,6 +64,8 @@
                                    SaltedProofIdHasher>>>
         pool;
 
+    size_t proofCount = 0;
+
 public:
     enum AddProofStatus {
         REJECTED = 0,   //!< Rejected due to conflicts
@@ -104,6 +106,7 @@
     ProofRef getProof(const COutPoint &outpoint) const;
 
     size_t size() const { return pool.size(); }
+    size_t getProofCount() const { return proofCount; }
 };
 
 } // namespace avalanche
diff --git a/src/avalanche/proofpool.cpp b/src/avalanche/proofpool.cpp
--- a/src/avalanche/proofpool.cpp
+++ b/src/avalanche/proofpool.cpp
@@ -46,6 +46,8 @@
         return AddProofStatus::REJECTED;
     }
 
+    proofCount++;
+
     return AddProofStatus::SUCCEED;
 }
 
@@ -76,12 +78,18 @@
 // loop so we pass it by value.
 bool ProofPool::removeProof(ProofId proofid) {
     auto &poolView = pool.get<by_proofid>();
-    return poolView.erase(proofid);
+    if (!poolView.erase(proofid)) {
+        return false;
+    }
+
+    proofCount--;
+    return true;
 }
 
 void ProofPool::rescan(PeerManager &peerManager) {
     auto previousPool = std::move(pool);
     pool.clear();
+    proofCount = 0;
 
     for (auto &entry : previousPool) {
         peerManager.registerProof(entry.proof);
diff --git a/src/avalanche/test/proofpool_tests.cpp b/src/avalanche/test/proofpool_tests.cpp
--- a/src/avalanche/test/proofpool_tests.cpp
+++ b/src/avalanche/test/proofpool_tests.cpp
@@ -277,4 +277,106 @@
     }
 }
 
+BOOST_AUTO_TEST_CASE(proof_count) {
+    ProofPool testPool;
+
+    BOOST_CHECK_EQUAL(testPool.getProofCount(), 0);
+
+    std::vector<ProofRef> proofs;
+
+    for (size_t i = 0; i < 10; i++) {
+        auto proof = buildRandomProof(MIN_VALID_PROOF_SCORE);
+
+        BOOST_CHECK_EQUAL(testPool.getProofCount(), i);
+        BOOST_CHECK_EQUAL(testPool.addProofIfNoConflict(proof),
+                          ProofPool::AddProofStatus::SUCCEED);
+        BOOST_CHECK_EQUAL(testPool.getProofCount(), i + 1);
+
+        proofs.emplace_back(std::move(proof));
+    }
+
+    // Attempting to add duplicated proofs doesn't change the count
+    for (const auto &proof : proofs) {
+        BOOST_CHECK_EQUAL(testPool.addProofIfNoConflict(proof),
+                          ProofPool::AddProofStatus::DUPLICATED);
+        BOOST_CHECK_EQUAL(testPool.addProofIfPreferred(proof),
+                          ProofPool::AddProofStatus::DUPLICATED);
+        BOOST_CHECK_EQUAL(testPool.getProofCount(), proofs.size());
+    }
+
+    for (size_t i = 0; i < 10; i++) {
+        BOOST_CHECK_EQUAL(testPool.getProofCount(), 10 - i);
+        BOOST_CHECK(testPool.removeProof(proofs.back()->getId()));
+        BOOST_CHECK_EQUAL(testPool.getProofCount(), 10 - i - 1);
+
+        proofs.pop_back();
+    }
+
+    // Attempting to remove non existing proofs doesn't change the count
+    for (size_t i = 0; i < 10; i++) {
+        auto proof = buildRandomProof(MIN_VALID_PROOF_SCORE);
+        BOOST_CHECK(!testPool.removeProof(proof->getId()));
+        BOOST_CHECK_EQUAL(testPool.getProofCount(), 0);
+    }
+
+    // Build several proofs with 2 UTXOS each, then one proof with a higher
+    // sequence number that conflict with each of these proofs.
+
+    std::vector<ProofRef> conflictingProofs;
+    const CKey key = CKey::MakeCompressedKey();
+    std::vector<COutPoint> conflictingOutpoints;
+    for (size_t i = 0; i < 10; i++) {
+        const COutPoint outpoint1{TxId(GetRandHash()), 0};
+        const COutPoint outpoint2{TxId(GetRandHash()), 0};
+
+        {
+            // Use sequence = 1
+            ProofBuilder pb(1, 0, key);
+            BOOST_CHECK(pb.addUTXO(outpoint1, 10 * COIN, 123456, false, key));
+            BOOST_CHECK(pb.addUTXO(outpoint2, 10 * COIN, 123456, false, key));
+            conflictingProofs.emplace_back(pb.build());
+        }
+
+        conflictingOutpoints.push_back(std::move(outpoint1));
+    }
+
+    BOOST_CHECK_EQUAL(conflictingProofs.size(), 10);
+    BOOST_CHECK_EQUAL(testPool.getProofCount(), 0);
+
+    // Add all the conflicting proofs, that will be lated replaced
+    for (size_t i = 0; i < 10; i++) {
+        BOOST_CHECK_EQUAL(testPool.addProofIfPreferred(conflictingProofs[i]),
+                          ProofPool::AddProofStatus::SUCCEED);
+        BOOST_CHECK_EQUAL(testPool.getProofCount(), i + 1);
+    }
+
+    // Register the replacement proof
+    {
+        // Use sequence = 2
+        ProofBuilder pb(2, 0, key);
+        for (const auto &outpoint : conflictingOutpoints) {
+            BOOST_CHECK(pb.addUTXO(outpoint, 10 * COIN, 123456, false, key));
+        }
+        auto proof = pb.build();
+
+        BOOST_CHECK_EQUAL(testPool.addProofIfPreferred(proof),
+                          ProofPool::AddProofStatus::SUCCEED);
+
+        // The pool now contains a single proof
+        BOOST_CHECK_EQUAL(testPool.getProofCount(), 1);
+        BOOST_CHECK(testPool.getProof(proof->getId()) == proof);
+        for (const auto &conflictingProof : conflictingProofs) {
+            BOOST_CHECK(testPool.getProof(conflictingProof->getId()) ==
+                        nullptr);
+        }
+    }
+
+    BOOST_CHECK_EQUAL(testPool.getProofCount(), 1);
+
+    // Rescan should reset the counter of no proof is added back to the pool
+    avalanche::PeerManager pm;
+    testPool.rescan(pm);
+    BOOST_CHECK_EQUAL(testPool.getProofCount(), 0);
+}
+
 BOOST_AUTO_TEST_SUITE_END()