diff --git a/src/Makefile.test.include b/src/Makefile.test.include
--- a/src/Makefile.test.include
+++ b/src/Makefile.test.include
@@ -191,6 +191,7 @@
   test/util_tests.cpp \
   test/validation_block_tests.cpp \
   test/validation_tests.cpp \
+  test/validationinterface_tests.cpp \
   test/versionbits_tests.cpp \
   test/work_comparator_tests.cpp \
   rpc/test/server_tests.cpp
diff --git a/src/test/CMakeLists.txt b/src/test/CMakeLists.txt
--- a/src/test/CMakeLists.txt
+++ b/src/test/CMakeLists.txt
@@ -192,6 +192,7 @@
 		util_threadnames_tests.cpp
 		validation_block_tests.cpp
 		validation_tests.cpp
+		validationinterface_tests.cpp
 		versionbits_tests.cpp
 		work_comparator_tests.cpp
 
diff --git a/src/test/validationinterface_tests.cpp b/src/test/validationinterface_tests.cpp
new file mode 100644
--- /dev/null
+++ b/src/test/validationinterface_tests.cpp
@@ -0,0 +1,62 @@
+// Copyright (c) 2020 The Bitcoin Core developers
+// Distributed under the MIT software license, see the accompanying
+// file COPYING or http://www.opensource.org/licenses/mit-license.php.
+
+#include <boost/test/unit_test.hpp>
+
+#include <consensus/validation.h>
+#include <primitives/block.h>
+#include <scheduler.h>
+#include <util/check.h>
+#include <validationinterface.h>
+
+BOOST_AUTO_TEST_SUITE(validationinterface_tests)
+
+class TestInterface : public CValidationInterface {
+public:
+    TestInterface(std::function<void()> on_call = nullptr,
+                  std::function<void()> on_destroy = nullptr)
+        : m_on_call(std::move(on_call)), m_on_destroy(std::move(on_destroy)) {}
+    virtual ~TestInterface() {
+        if (m_on_destroy) {
+            m_on_destroy();
+        }
+    }
+    void BlockChecked(const CBlock &block,
+                      const CValidationState &state) override {
+        if (m_on_call) {
+            m_on_call();
+        }
+    }
+    static void Call() {
+        CBlock block;
+        CValidationState state;
+        GetMainSignals().BlockChecked(block, state);
+    }
+    std::function<void()> m_on_call;
+    std::function<void()> m_on_destroy;
+};
+
+// Regression test to ensure UnregisterAllValidationInterfaces calls don't
+// destroy a validation interface while it is being called. Bug:
+// https://github.com/bitcoin/bitcoin/pull/18551
+BOOST_AUTO_TEST_CASE(unregister_all_during_call) {
+    bool destroyed = false;
+
+    CScheduler scheduler;
+    GetMainSignals().RegisterBackgroundSignalScheduler(scheduler);
+    RegisterSharedValidationInterface(std::make_shared<TestInterface>(
+        [&] {
+            // First call should decrements reference count 2 -> 1
+            UnregisterAllValidationInterfaces();
+            BOOST_CHECK(!destroyed);
+            // Second call should not decrement reference count 1 -> 0
+            UnregisterAllValidationInterfaces();
+            BOOST_CHECK(!destroyed);
+        },
+        [&] { destroyed = true; }));
+    TestInterface::Call();
+    BOOST_CHECK(destroyed);
+}
+
+BOOST_AUTO_TEST_SUITE_END()
diff --git a/src/validationinterface.cpp b/src/validationinterface.cpp
--- a/src/validationinterface.cpp
+++ b/src/validationinterface.cpp
@@ -75,8 +75,8 @@
     //! executing.
     void Clear() {
         LOCK(m_mutex);
-        for (auto it = m_list.begin(); it != m_list.end();) {
-            it = --it->count ? std::next(it) : m_list.erase(it);
+        for (const auto &entry : m_map) {
+            if (!--entry.second->count) m_list.erase(entry.second);
         }
         m_map.clear();
     }