diff --git a/src/net_processing.cpp b/src/net_processing.cpp
--- a/src/net_processing.cpp
+++ b/src/net_processing.cpp
@@ -1716,21 +1716,21 @@
         g_avalanche->withPeerManager([&](avalanche::PeerManager &pm) {
             return pm.shouldRequestMoreNodes();
         })) {
-        // Randomly select an avalanche peer to send the getavaaddr message to
-        const NodeId avanodeId = avanode_ids.front();
-
-        m_connman.ForNode(avanodeId, [&](CNode *pavanode) {
-            LogPrint(BCLog::AVALANCHE,
-                     "Requesting more avalanche addresses from peer %d\n",
-                     avanodeId);
-            m_connman.PushMessage(pavanode,
-                                  CNetMsgMaker(pavanode->GetCommonVersion())
-                                      .Make(NetMsgType::GETAVAADDR));
-            PeerRef peer = GetPeerRef(avanodeId);
-            WITH_LOCK(peer->m_addr_token_bucket_mutex,
-                      peer->m_addr_token_bucket += GetMaxAddrToSend());
-            return true;
-        });
+        // Request avalanche addresses from our peers
+        for (NodeId avanodeId : avanode_ids) {
+            m_connman.ForNode(avanodeId, [&](CNode *pavanode) {
+                LogPrint(BCLog::AVALANCHE,
+                         "Requesting more avalanche addresses from peer %d\n",
+                         avanodeId);
+                m_connman.PushMessage(pavanode,
+                                      CNetMsgMaker(pavanode->GetCommonVersion())
+                                          .Make(NetMsgType::GETAVAADDR));
+                PeerRef peer = GetPeerRef(avanodeId);
+                WITH_LOCK(peer->m_addr_token_bucket_mutex,
+                          peer->m_addr_token_bucket += GetMaxAddrToSend());
+                return true;
+            });
+        }
     }
 
     if (m_chainman.ActiveChainstate().IsInitialBlockDownload()) {
diff --git a/test/functional/abc_p2p_getavaaddr.py b/test/functional/abc_p2p_getavaaddr.py
--- a/test/functional/abc_p2p_getavaaddr.py
+++ b/test/functional/abc_p2p_getavaaddr.py
@@ -252,15 +252,15 @@
         node.generate(1)
 
         # Because none of the avalanche peers is responding, our node should
-        # fail out of option shortly and send a getavaaddr message to one of its
+        # fail out of option shortly and send a getavaaddr message to its
         # outbound avalanche peers.
         node.mockscheduler(MAX_GETAVAADDR_DELAY)
 
-        def any_peer_received_getavaaddr():
+        def all_peers_received_getavaaddr():
             with p2p_lock:
-                return any([p.message_count.get(
+                return all([p.message_count.get(
                     "getavaaddr", 0) > 1 for p in avapeers])
-        self.wait_until(any_peer_received_getavaaddr)
+        self.wait_until(all_peers_received_getavaaddr)
 
     def getavaaddr_manual_test(self):
         self.log.info(