diff --git a/src/avalanche/peermanager.h b/src/avalanche/peermanager.h
--- a/src/avalanche/peermanager.h
+++ b/src/avalanche/peermanager.h
@@ -95,6 +95,11 @@
     result_type operator()(const Peer &p) const { return p.proof->getId(); }
 };
 
+struct score_index {
+    using result_type = uint32_t;
+    result_type operator()(const Peer &p) const { return p.getScore(); }
+};
+
 struct next_request_time {};
 
 struct PendingNode {
@@ -107,6 +112,7 @@
 
 struct by_proofid;
 struct by_nodeid;
+struct by_score;
 
 namespace bmi = boost::multi_index;
 
@@ -125,7 +131,10 @@
                   bmi::hashed_unique<bmi::member<Peer, PeerId, &Peer::peerid>>,
                   // index by proof
                   bmi::hashed_unique<bmi::tag<proof_index>, proof_index,
-                                     SaltedProofIdHasher>>>;
+                                     SaltedProofIdHasher>,
+                  // ordered by score, decreasing order
+                  bmi::ordered_non_unique<bmi::tag<by_score>, score_index,
+                                          std::greater<uint32_t>>>>;
 
     PeerId nextPeerId = 0;
     PeerSet peers;
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
@@ -29,6 +29,17 @@
             auto &pendingNodesView = pm.pendingNodes.get<by_nodeid>();
             return pendingNodesView.find(nodeid) != pendingNodesView.end();
         }
+
+        static std::vector<uint32_t> getOrderedScores(const PeerManager &pm) {
+            std::vector<uint32_t> scores;
+
+            auto &peerView = pm.peers.get<by_score>();
+            for (const Peer &peer : peerView) {
+                scores.push_back(peer.getScore());
+            }
+
+            return scores;
+        }
     };
 } // namespace
 } // namespace avalanche
@@ -788,4 +799,29 @@
         !pm.registerProof(std::make_shared<Proof>(std::move(badProof))));
 }
 
+BOOST_AUTO_TEST_CASE(score_oredering) {
+    avalanche::PeerManager pm;
+
+    std::vector<uint32_t> scores(10);
+    std::generate(scores.begin(), scores.end(),
+                  [n = 1]() mutable { return n++ * MIN_VALID_PROOF_SCORE; });
+
+    std::vector<std::shared_ptr<Proof>> proofs;
+    proofs.reserve(scores.size());
+    for (uint32_t score : scores) {
+        proofs.push_back(getRandomProofPtr(score));
+    }
+
+    // Shuffle the proofs so they are registered in a random score order
+    Shuffle(proofs.begin(), proofs.end(), FastRandomContext());
+    for (auto &proof : proofs) {
+        BOOST_CHECK(pm.registerProof(proof));
+    }
+
+    auto peersScores = TestPeerManager::getOrderedScores(pm);
+    // Expect the peers to be ordered by descending score
+    BOOST_CHECK_EQUAL_COLLECTIONS(peersScores.begin(), peersScores.end(),
+                                  scores.rbegin(), scores.rend());
+}
+
 BOOST_AUTO_TEST_SUITE_END()