diff --git a/src/bench/CMakeLists.txt b/src/bench/CMakeLists.txt
--- a/src/bench/CMakeLists.txt
+++ b/src/bench/CMakeLists.txt
@@ -67,6 +67,7 @@
 	rpc_blockchain.cpp
 	rpc_mempool.cpp
 	streams_findbyte.cpp
+	strencodings.cpp
 	util_time.cpp
 	verify_script.cpp
 
diff --git a/src/bench/strencodings.cpp b/src/bench/strencodings.cpp
new file mode 100644
--- /dev/null
+++ b/src/bench/strencodings.cpp
@@ -0,0 +1,17 @@
+// Copyright (c) 2022 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 <bench/bench.h>
+#include <bench/data.h>
+#include <util/strencodings.h>
+
+static void HexStrBench(benchmark::Bench &bench) {
+    auto const &data = benchmark::data::block413567;
+    bench.batch(data.size()).unit("byte").run([&] {
+        auto hex = HexStr(data);
+        ankerl::nanobench::doNotOptimizeAway(hex);
+    });
+}
+
+BENCHMARK(HexStrBench);
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
@@ -245,6 +245,24 @@
         BOOST_CHECK_EQUAL(HexStr(in_s), out_exp);
         BOOST_CHECK_EQUAL(HexStr(in_b), out_exp);
     }
+
+    {
+        auto input = std::string();
+        for (size_t i = 0; i < 256; ++i) {
+            input.push_back(static_cast<char>(i));
+        }
+
+        auto hex = HexStr(input);
+        BOOST_TEST_REQUIRE(hex.size() == 512);
+        static constexpr auto hexmap = std::string_view("0123456789abcdef");
+        for (size_t i = 0; i < 256; ++i) {
+            auto upper = hexmap.find(hex[i * 2]);
+            auto lower = hexmap.find(hex[i * 2 + 1]);
+            BOOST_TEST_REQUIRE(upper != std::string_view::npos);
+            BOOST_TEST_REQUIRE(lower != std::string_view::npos);
+            BOOST_TEST_REQUIRE(i == upper * 16 + lower);
+        }
+    }
 }
 
 BOOST_AUTO_TEST_CASE(span_write_bytes) {
diff --git a/src/util/strencodings.cpp b/src/util/strencodings.cpp
--- a/src/util/strencodings.cpp
+++ b/src/util/strencodings.cpp
@@ -8,6 +8,7 @@
 
 #include <tinyformat.h>
 
+#include <array>
 #include <cstdlib>
 #include <cstring>
 #include <optional>
@@ -521,15 +522,35 @@
     return str;
 }
 
+namespace {
+
+using ByteAsHex = std::array<char, 2>;
+
+constexpr std::array<ByteAsHex, 256> CreateByteToHexMap() {
+    constexpr char hexmap[16] = {'0', '1', '2', '3', '4', '5', '6', '7',
+                                 '8', '9', 'a', 'b', 'c', 'd', 'e', 'f'};
+
+    std::array<ByteAsHex, 256> byte_to_hex{};
+    for (size_t i = 0; i < byte_to_hex.size(); ++i) {
+        byte_to_hex[i][0] = hexmap[i >> 4];
+        byte_to_hex[i][1] = hexmap[i & 15];
+    }
+    return byte_to_hex;
+}
+
+} // namespace
+
 std::string HexStr(const Span<const uint8_t> s) {
     std::string rv(s.size() * 2, '\0');
-    static constexpr char hexmap[16] = {'0', '1', '2', '3', '4', '5', '6', '7',
-                                        '8', '9', 'a', 'b', 'c', 'd', 'e', 'f'};
-    auto it = rv.begin();
+    static constexpr auto byte_to_hex = CreateByteToHexMap();
+    static_assert(sizeof(byte_to_hex) == 512);
+
+    char *it = rv.data();
     for (uint8_t v : s) {
-        *it++ = hexmap[v >> 4];
-        *it++ = hexmap[v & 15];
+        std::memcpy(it, byte_to_hex[v].data(), 2);
+        it += 2;
     }
-    assert(it == rv.end());
+
+    assert(it == rv.data() + rv.size());
     return rv;
 }