diff --git a/src/net_processing.cpp b/src/net_processing.cpp
--- a/src/net_processing.cpp
+++ b/src/net_processing.cpp
@@ -1714,14 +1714,15 @@
         goto scheduleLater;
     }
 
+    Shuffle(avanode_outbound_ids.begin(), avanode_outbound_ids.end(),
+            FastRandomContext());
+
     if (!g_avalanche->isQuorumEstablished() ||
         g_avalanche->withPeerManager([&](avalanche::PeerManager &pm) {
             return pm.shouldRequestMoreNodes();
         })) {
         // Randomly select an avalanche outbound peer to send the getavaaddr
         // message to
-        Shuffle(avanode_outbound_ids.begin(), avanode_outbound_ids.end(),
-                FastRandomContext());
         const NodeId avanodeId = avanode_outbound_ids.front();
 
         m_connman.ForNode(avanodeId, [&](CNode *pavanode) {
@@ -1738,6 +1739,16 @@
         });
     }
 
+    // Send a getavaproofs to one of our peers
+    m_connman.ForNode(avanode_outbound_ids.back(), [&](CNode *pavanode) {
+        LogPrint(BCLog::AVALANCHE, "Requesting compact proofs from peer %d\n",
+                 pavanode->GetId());
+        m_connman.PushMessage(pavanode,
+                              CNetMsgMaker(pavanode->GetCommonVersion())
+                                  .Make(NetMsgType::GETAVAPROOFS));
+        return true;
+    });
+
 scheduleLater:
     // Schedule next run for 2-5 minutes in the future.
     // We add randomness on every cycle to avoid the possibility of P2P
diff --git a/test/functional/abc_p2p_compactproofs.py b/test/functional/abc_p2p_compactproofs.py
--- a/test/functional/abc_p2p_compactproofs.py
+++ b/test/functional/abc_p2p_compactproofs.py
@@ -99,7 +99,26 @@
         self.wait_until(
             lambda: all([p.last_message.get("getavaproofs") for p in outbound_avapeers]))
         assert all([p.message_count.get(
-            "getavaproofs", 0) == 1 for p in outbound_avapeers])
+            "getavaproofs", 0) >= 1 for p in outbound_avapeers])
+        assert all([p.message_count.get(
+            "getavaproofs", 0) == 0 for p in non_avapeers])
+        assert all([p.message_count.get(
+            "getavaproofs", 0) == 0 for p in inbound_avapeers])
+
+        self.log.info(
+            "Check we send periodic getavaproofs message to one of our peers")
+
+        def count_outbounds_getavaproofs():
+            return sum([p.message_count.get("getavaproofs", 0)
+                       for p in outbound_avapeers])
+
+        outbounds_getavaproofs = count_outbounds_getavaproofs()
+        for i in range(12):
+            node.mockscheduler(AVALANCHE_MAX_PERIODIC_NETWORKING_INTERVAL)
+            self.wait_until(lambda: count_outbounds_getavaproofs()
+                            == outbounds_getavaproofs + 1)
+            outbounds_getavaproofs += 1
+
         assert all([p.message_count.get(
             "getavaproofs", 0) == 0 for p in non_avapeers])
         assert all([p.message_count.get(