diff --git a/src/net_processing.cpp b/src/net_processing.cpp
--- a/src/net_processing.cpp
+++ b/src/net_processing.cpp
@@ -5331,12 +5331,13 @@
         };
 
         // Get up to MAX_ADDR_TO_SEND addresses of the nodes which are the
-        // most active in the avalanche network.
+        // most active in the avalanche network. Account for 0 availability as
+        // well so we can send addresses even if we did not start polling yet.
         std::set<const CNode *, decltype(availabilityScoreComparator)> avaNodes(
             availabilityScoreComparator);
         m_connman.ForEachNode([&](const CNode *pnode) {
             if (pnode && pnode->m_avalanche_state &&
-                pnode->m_avalanche_state->getAvailabilityScore() > 0.) {
+                !(pnode->m_avalanche_state->getAvailabilityScore() < 0.)) {
                 avaNodes.insert(pnode);
                 if (avaNodes.size() > GetMaxAddrToSend()) {
                     avaNodes.erase(std::prev(avaNodes.end()));
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
@@ -4,6 +4,7 @@
 # file COPYING or http://www.opensource.org/licenses/mit-license.php.
 """Test getavaaddr p2p message"""
 import time
+from decimal import Decimal
 
 from test_framework.avatools import AvaP2PInterface, gen_proof
 from test_framework.key import ECKey
@@ -17,6 +18,7 @@
 from test_framework.p2p import P2PInterface, p2p_lock
 from test_framework.test_framework import BitcoinTestFramework
 from test_framework.util import assert_equal
+from test_framework.wallet_util import bytes_to_wif
 
 # getavaaddr time interval in seconds, as defined in net_processing.cpp
 GETAVAADDR_INTERVAL = 10 * 60
@@ -253,8 +255,7 @@
             '-avaminquorumconnectedstakeratio=0.8',
         ])
 
-        privkey = ECKey()
-        privkey.generate()
+        privkey, proof = gen_proof(node)
 
         avapeers = []
         for i in range(16):
@@ -267,6 +268,9 @@
             )
             avapeers.append(avapeer)
 
+            peerinfo = node.getpeerinfo()[-1]
+            avapeer.set_addr(peerinfo["addr"])
+
         self.wait_until(
             lambda: all([p.last_message.get("getavaaddr") for p in avapeers]))
         assert all([p.message_count.get(
@@ -279,6 +283,41 @@
             self.wait_until(
                 lambda: any([p.message_count.get("getavaaddr", 0) > 1 for p in avapeers]))
 
+        # Connect the nodes via an avahello message
+        limitedproofid_hex = f"{proof.limited_proofid:0{64}x}"
+        for avapeer in avapeers:
+            avakey = ECKey()
+            avakey.generate()
+            delegation = node.delegateavalancheproof(
+                limitedproofid_hex,
+                bytes_to_wif(privkey.get_bytes()),
+                avakey.get_pubkey().get_bytes().hex(),
+            )
+            avapeer.send_avahello(delegation, avakey)
+
+        # Move the schedulter time forward to make seure we get statistics
+        # computed. But since we did not start polling yet it should remain all
+        # zero.
+        node.mockscheduler(10 * 60)
+
+        def wait_for_availability_score():
+            peerinfo = node.getpeerinfo()
+            return all([p.get('availability_score', None) == Decimal(0)
+                       for p in peerinfo])
+        self.wait_until(wait_for_availability_score)
+
+        requester = node.add_p2p_connection(AddrReceiver())
+        requester.send_and_ping(msg_getavaaddr())
+
+        node.setmocktime(int(time.time() + 5 * 60))
+
+        # Check all the peers addresses are returned.
+        requester.wait_until(requester.addr_received)
+        addresses = requester.get_received_addrs()
+        assert_equal(len(addresses), len(avapeers))
+        expected_addresses = [avapeer.addr for avapeer in avapeers]
+        assert all([address in expected_addresses for address in addresses])
+
     def run_test(self):
         self.getavaaddr_interval_test()
 
diff --git a/test/functional/test_framework/avatools.py b/test/functional/test_framework/avatools.py
--- a/test/functional/test_framework/avatools.py
+++ b/test/functional/test_framework/avatools.py
@@ -187,6 +187,15 @@
 
         return create_conn
 
+    def peer_accept_connection(self, *args, **kwargs):
+        create_conn = super().peer_accept_connection(*args, **kwargs)
+
+        # Save the nonce and extra entropy so they can be reused later.
+        self.local_nonce = self.on_connection_send_msg.nNonce
+        self.local_extra_entropy = self.on_connection_send_msg.nExtraEntropy
+
+        return create_conn
+
     def on_version(self, message):
         super().on_version(message)