diff --git a/src/test/util_tests.cpp b/src/test/util_tests.cpp
--- a/src/test/util_tests.cpp
+++ b/src/test/util_tests.cpp
@@ -180,6 +180,23 @@
                       "FOO, BAR");
 }
 
+BOOST_AUTO_TEST_CASE(util_ReplaceAll) {
+    const std::string original("A test \"%s\" string '%s'.");
+    auto test_replaceall = [&original](const std::string &search,
+                                       const std::string &substitute,
+                                       const std::string &expected) {
+        auto test = original;
+        ReplaceAll(test, search, substitute);
+        BOOST_CHECK_EQUAL(test, expected);
+    };
+
+    test_replaceall("", "foo", original);
+    test_replaceall(original, "foo", "foo");
+    test_replaceall("%s", "foo", "A test \"foo\" string 'foo'.");
+    test_replaceall("\"", "foo", "A test foo%sfoo string '%s'.");
+    test_replaceall("'", "foo", "A test \"%s\" string foo%sfoo.");
+}
+
 BOOST_AUTO_TEST_CASE(util_FormatParseISO8601DateTime) {
     BOOST_CHECK_EQUAL(FormatISO8601DateTime(1317425777),
                       "2011-09-30T23:36:17Z");
diff --git a/src/util/string.h b/src/util/string.h
--- a/src/util/string.h
+++ b/src/util/string.h
@@ -14,8 +14,8 @@
 #include <string>
 #include <vector>
 
-void ReplaceAll(std::string &in_out, std::string_view search,
-                std::string_view substitute);
+void ReplaceAll(std::string &in_out, const std::string &search,
+                const std::string &substitute);
 
 [[nodiscard]] inline std::string
 TrimString(const std::string &str, const std::string &pattern = " \f\n\r\t\v") {
diff --git a/src/util/string.cpp b/src/util/string.cpp
--- a/src/util/string.cpp
+++ b/src/util/string.cpp
@@ -4,9 +4,13 @@
 
 #include <util/string.h>
 
-#include <boost/algorithm/string/replace.hpp>
+#include <regex>
+#include <string>
 
-void ReplaceAll(std::string &in_out, std::string_view search,
-                std::string_view substitute) {
-    boost::replace_all(in_out, search, substitute);
+void ReplaceAll(std::string &in_out, const std::string &search,
+                const std::string &substitute) {
+    if (search.empty()) {
+        return;
+    }
+    in_out = std::regex_replace(in_out, std::regex(search), substitute);
 }
diff --git a/test/lint/lint-boost-dependencies.sh b/test/lint/lint-boost-dependencies.sh
--- a/test/lint/lint-boost-dependencies.sh
+++ b/test/lint/lint-boost-dependencies.sh
@@ -11,7 +11,6 @@
 EXPECTED_BOOST_INCLUDES=(
     boost/algorithm/string.hpp
     boost/algorithm/string/classification.hpp
-    boost/algorithm/string/replace.hpp
     boost/algorithm/string/split.hpp
     boost/date_time/posix_time/posix_time.hpp
     boost/mpl/list.hpp