diff --git a/src/init.cpp b/src/init.cpp
--- a/src/init.cpp
+++ b/src/init.cpp
@@ -212,8 +212,20 @@
     if (node.peer_logic) {
         UnregisterValidationInterface(node.peer_logic.get());
     }
+    // Follow the lock order requirements:
+    // * CheckForStaleTipAndEvictPeers locks cs_main before indirectly calling
+    //   GetExtraOutboundCount which locks cs_vNodes.
+    // * ProcessMessage locks cs_main and g_cs_orphans before indirectly calling
+    //   ForEachNode which locks cs_vNodes.
+    // * CConnman::Stop calls DeleteNode, which calls FinalizeNode, which locks
+    //   cs_main and calls EraseOrphansFor, which locks g_cs_orphans.
+    //
+    // Thus the implicit locking order requirement is:
+    // (1) cs_main, (2) g_cs_orphans, (3) cs_vNodes.
     if (node.connman) {
-        node.connman->Stop();
+        node.connman->StopThreads();
+        LOCK2(::cs_main, ::g_cs_orphans);
+        node.connman->StopNodes();
     }
     if (g_txindex) {
         g_txindex->Stop();
diff --git a/src/net.h b/src/net.h
--- a/src/net.h
+++ b/src/net.h
@@ -206,19 +206,12 @@
 
     bool Start(CScheduler &scheduler, const Options &options);
 
-    // TODO: Remove NO_THREAD_SAFETY_ANALYSIS. Lock cs_vNodes before reading the
-    // variable vNodes.
-    //
-    // When removing NO_THREAD_SAFETY_ANALYSIS be aware of the following lock
-    // order requirements:
-    // * CheckForStaleTipAndEvictPeers locks cs_main before indirectly calling
-    //   GetExtraOutboundCount which locks cs_vNodes.
-    // * ProcessMessage locks cs_main and g_cs_orphans before indirectly calling
-    //   ForEachNode which locks cs_vNodes.
-    //
-    // Thus the implicit locking order requirement is: (1) cs_main, (2)
-    // g_cs_orphans, (3) cs_vNodes.
-    void Stop() NO_THREAD_SAFETY_ANALYSIS;
+    void StopThreads();
+    void StopNodes();
+    void Stop() {
+        StopThreads();
+        StopNodes();
+    };
 
     void Interrupt();
     bool GetNetworkActive() const { return fNetworkActive; };
diff --git a/src/net.cpp b/src/net.cpp
--- a/src/net.cpp
+++ b/src/net.cpp
@@ -2622,7 +2622,7 @@
     }
 }
 
-void CConnman::Stop() {
+void CConnman::StopThreads() {
     if (threadMessageHandler.joinable()) {
         threadMessageHandler.join();
     }
@@ -2638,13 +2638,16 @@
     if (threadSocketHandler.joinable()) {
         threadSocketHandler.join();
     }
+}
 
+void CConnman::StopNodes() {
     if (fAddressesInitialized) {
         DumpAddresses();
         fAddressesInitialized = false;
     }
 
     // Close sockets
+    LOCK(cs_vNodes);
     for (CNode *pnode : vNodes) {
         pnode->CloseSocketDisconnect();
     }
diff --git a/src/net_processing.h b/src/net_processing.h
--- a/src/net_processing.h
+++ b/src/net_processing.h
@@ -12,6 +12,7 @@
 #include <validationinterface.h>
 
 extern RecursiveMutex cs_main;
+extern RecursiveMutex g_cs_orphans;
 
 class Config;
 
diff --git a/src/test/denialofservice_tests.cpp b/src/test/denialofservice_tests.cpp
--- a/src/test/denialofservice_tests.cpp
+++ b/src/test/denialofservice_tests.cpp
@@ -51,7 +51,6 @@
     NodeId fromPeer;
     int64_t nTimeExpire;
 };
-extern RecursiveMutex g_cs_orphans;
 extern std::map<uint256, COrphanTx>
     mapOrphanTransactions GUARDED_BY(g_cs_orphans);