diff --git a/http/routing.hpp b/http/routing.hpp
index 4a03a53..8852b30 100644
--- a/http/routing.hpp
+++ b/http/routing.hpp
@@ -27,6 +27,19 @@
 namespace crow
 {
 
+// Note, this is an imperfect abstraction.  There are a lot of verbs that we
+// use memory for, but are basically unused by most implementations.
+// Ideally we would have a list of verbs that we do use, and only index in
+// to a smaller array of those, but that would require a translation from
+// boost::beast::http::verb, to the bmcweb index.
+static constexpr size_t maxVerbIndex =
+    static_cast<size_t>(boost::beast::http::verb::patch);
+
+// MaxVerb + 1 is designated as the "not found" verb.  It is done this way
+// to keep the BaseRule as a single bitfield (thus keeping the struct small)
+// while still having a way to declare a route a "not found" route.
+static constexpr const size_t notFoundIndex = maxVerbIndex + 1;
+
 class BaseRule
 {
   public:
@@ -95,6 +108,9 @@
 
     size_t methodsBitfield{
         1 << static_cast<size_t>(boost::beast::http::verb::get)};
+    static_assert(std::numeric_limits<decltype(methodsBitfield)>::digits >
+                      notFoundIndex,
+                  "Not enough bits to store bitfield");
 
     std::vector<redfish::Privileges> privilegesSet;
 
@@ -441,6 +457,13 @@
         return *self;
     }
 
+    self_t& notFound()
+    {
+        self_t* self = static_cast<self_t*>(this);
+        self->methodsBitfield = 1U << notFoundIndex;
+        return *self;
+    }
+
     self_t& privileges(
         const std::initializer_list<std::initializer_list<const char*>>& p)
     {
@@ -1097,7 +1120,7 @@
         {
             return;
         }
-        for (size_t method = 0, methodBit = 1; method < maxHttpVerbCount;
+        for (size_t method = 0, methodBit = 1; method <= notFoundIndex;
              method++, methodBit <<= 1)
         {
             if ((ruleObject->methodsBitfield & methodBit) > 0U)
@@ -1140,6 +1163,53 @@
         }
     }
 
+    struct FindRoute
+    {
+        BaseRule* rule = nullptr;
+        RoutingParams params;
+    };
+
+    struct FindRouteResponse
+    {
+        std::string allowHeader;
+        FindRoute route;
+    };
+
+    FindRouteResponse findRoute(const Request& req) const
+    {
+        FindRouteResponse findRoute;
+
+        size_t reqMethodIndex = static_cast<size_t>(req.method());
+        // Check to see if this url exists at any verb
+        for (size_t perMethodIndex = 0; perMethodIndex <= maxVerbIndex;
+             perMethodIndex++)
+        {
+            // Make sure it's safe to deference the array at that index
+            static_assert(maxVerbIndex <
+                          std::tuple_size_v<decltype(perMethods)>);
+
+            const PerMethod& perMethod = perMethods[perMethodIndex];
+            std::pair<unsigned, RoutingParams> found2 =
+                perMethod.trie.find(req.url);
+            if (found2.first == 0)
+            {
+                continue;
+            }
+            if (!findRoute.allowHeader.empty())
+            {
+                findRoute.allowHeader += ", ";
+            }
+            findRoute.allowHeader += boost::beast::http::to_string(
+                static_cast<boost::beast::http::verb>(perMethodIndex));
+            if (perMethodIndex == reqMethodIndex)
+            {
+                findRoute.route.rule = perMethod.rules[found2.first];
+                findRoute.route.params = std::move(found2.second);
+            }
+        }
+        return findRoute;
+    }
+
     template <typename Adaptor>
     void handleUpgrade(const Request& req, Response& res, Adaptor&& adaptor)
     {
@@ -1209,30 +1279,6 @@
         }
     }
 
-    std::string buildAllowHeader(Request& req)
-    {
-        std::string allowHeader;
-        // Check to see if this url exists at any verb
-        for (size_t perMethodIndex = 0; perMethodIndex < perMethods.size();
-             perMethodIndex++)
-        {
-            const PerMethod& p = perMethods[perMethodIndex];
-            const std::pair<unsigned, RoutingParams>& found2 =
-                p.trie.find(req.url);
-            if (found2.first == 0)
-            {
-                continue;
-            }
-            if (!allowHeader.empty())
-            {
-                allowHeader += ", ";
-            }
-            allowHeader += boost::beast::http::to_string(
-                static_cast<boost::beast::http::verb>(perMethodIndex));
-        }
-        return allowHeader;
-    }
-
     void handle(Request& req,
                 const std::shared_ptr<bmcweb::AsyncResp>& asyncResp)
     {
@@ -1241,64 +1287,71 @@
             asyncResp->res.result(boost::beast::http::status::not_found);
             return;
         }
-        PerMethod& perMethod = perMethods[static_cast<size_t>(req.method())];
-        Trie& trie = perMethod.trie;
-        std::vector<BaseRule*>& rules = perMethod.rules;
-        std::string allowHeader = buildAllowHeader(req);
-        if (!allowHeader.empty())
+
+        FindRouteResponse foundRoute = findRoute(req);
+
+        // Couldn't find a normal route with any verb, try looking for a 404
+        // route
+        if (foundRoute.allowHeader.empty())
         {
+            if (foundRoute.route.rule == nullptr)
+            {
+                const PerMethod& perMethod = perMethods[notFoundIndex];
+                std::pair<unsigned, RoutingParams> found =
+                    perMethod.trie.find(req.url);
+                if (found.first >= perMethod.rules.size())
+                {
+                    throw std::runtime_error(
+                        "Trie internal structure corrupted!");
+                }
+                // Found a 404 route, switch that in
+                if (found.first != 0U)
+                {
+                    foundRoute.route.rule = perMethod.rules[found.first];
+                    foundRoute.route.params = std::move(found.second);
+                }
+            }
+        }
+        else
+        {
+            // Found at least one valid route, fill in the allow header
             asyncResp->res.addHeader(boost::beast::http::field::allow,
-                                     allowHeader);
+                                     foundRoute.allowHeader);
         }
 
-        const std::pair<unsigned, RoutingParams>& found = trie.find(req.url);
-
-        unsigned ruleIndex = found.first;
-        if (ruleIndex == 0U)
+        // If we couldn't find a real route or a 404 route, return a generic
+        // response
+        if (foundRoute.route.rule == nullptr)
         {
-            if (!allowHeader.empty())
+            if (foundRoute.allowHeader.empty())
+            {
+                asyncResp->res.result(boost::beast::http::status::not_found);
+            }
+            else
             {
                 asyncResp->res.result(
                     boost::beast::http::status::method_not_allowed);
-                return;
             }
-
-            BMCWEB_LOG_DEBUG << "Cannot match rules " << req.url;
-            asyncResp->res.result(boost::beast::http::status::not_found);
             return;
         }
 
-        if (ruleIndex >= rules.size())
-        {
-            throw std::runtime_error("Trie internal structure corrupted!");
-        }
+        BaseRule& rule = *foundRoute.route.rule;
+        RoutingParams params = std::move(foundRoute.route.params);
 
-        if ((rules[ruleIndex]->getMethods() &
-             (1U << static_cast<uint32_t>(req.method()))) == 0)
-        {
-            BMCWEB_LOG_DEBUG << "Rule found but method mismatch: " << req.url
-                             << " with " << req.methodString() << "("
-                             << static_cast<uint32_t>(req.method()) << ") / "
-                             << rules[ruleIndex]->getMethods();
-            asyncResp->res.result(
-                boost::beast::http::status::method_not_allowed);
-            return;
-        }
-
-        BMCWEB_LOG_DEBUG << "Matched rule '" << rules[ruleIndex]->rule << "' "
+        BMCWEB_LOG_DEBUG << "Matched rule '" << rule.rule << "' "
                          << static_cast<uint32_t>(req.method()) << " / "
-                         << rules[ruleIndex]->getMethods();
+                         << rule.getMethods();
 
         if (req.session == nullptr)
         {
-            rules[ruleIndex]->handle(req, asyncResp, found.second);
+            rule.handle(req, asyncResp, params);
             return;
         }
 
         crow::connections::systemBus->async_method_call(
-            [&req, asyncResp, &rules, ruleIndex,
-             found](const boost::system::error_code ec,
-                    const dbus::utility::DBusPropertiesMap& userInfoMap) {
+            [&req, asyncResp, &rule,
+             params](const boost::system::error_code ec,
+                     const dbus::utility::DBusPropertiesMap& userInfoMap) {
             if (ec)
             {
                 BMCWEB_LOG_ERROR << "GetUserInfo failed...";
@@ -1380,7 +1433,7 @@
                 BMCWEB_LOG_DEBUG << "Operation limited to ConfigureSelf";
             }
 
-            if (!rules[ruleIndex]->checkPrivileges(userPrivileges))
+            if (!rule.checkPrivileges(userPrivileges))
             {
                 asyncResp->res.result(boost::beast::http::status::forbidden);
                 if (req.session->isConfigureSelfOnly)
@@ -1394,7 +1447,7 @@
             }
 
             req.userRole = userRole;
-            rules[ruleIndex]->handle(req, asyncResp, found.second);
+            rule.handle(req, asyncResp, params);
             },
             "xyz.openbmc_project.User.Manager", "/xyz/openbmc_project/user",
             "xyz.openbmc_project.User.Manager", "GetUserInfo",
@@ -1438,10 +1491,7 @@
         {}
     };
 
-    const static size_t maxHttpVerbCount =
-        static_cast<size_t>(boost::beast::http::verb::unlink);
-
-    std::array<PerMethod, maxHttpVerbCount> perMethods;
+    std::array<PerMethod, notFoundIndex + 1> perMethods;
     std::vector<std::unique_ptr<BaseRule>> allRules;
 };
 } // namespace crow
diff --git a/http/ut/router_test.cpp b/http/ut/router_test.cpp
index 4d1a744..b43b659 100644
--- a/http/ut/router_test.cpp
+++ b/http/ut/router_test.cpp
@@ -42,17 +42,53 @@
 
     // No route should return no methods.
     router.validate();
-    EXPECT_EQ(router.buildAllowHeader(req), "");
+    EXPECT_EQ(router.findRoute(req).allowHeader, "");
+    EXPECT_EQ(router.findRoute(req).route.rule, nullptr);
 
     router.newRuleTagged<getParameterTag(url)>(std::string(url))
         .methods(boost::beast::http::verb::get)(nullCallback);
     router.validate();
-    EXPECT_EQ(router.buildAllowHeader(req), "GET");
+    EXPECT_EQ(router.findRoute(req).allowHeader, "GET");
+    EXPECT_NE(router.findRoute(req).route.rule, nullptr);
+
+    Request patchReq{{boost::beast::http::verb::patch, url, 11}, ec};
+    EXPECT_EQ(router.findRoute(patchReq).route.rule, nullptr);
 
     router.newRuleTagged<getParameterTag(url)>(std::string(url))
         .methods(boost::beast::http::verb::patch)(nullCallback);
     router.validate();
-    EXPECT_EQ(router.buildAllowHeader(req), "GET, PATCH");
+    EXPECT_EQ(router.findRoute(req).allowHeader, "GET, PATCH");
+    EXPECT_NE(router.findRoute(req).route.rule, nullptr);
+    EXPECT_NE(router.findRoute(patchReq).route.rule, nullptr);
+}
+
+TEST(Router, 404)
+{
+    bool notFoundCalled = false;
+    // Callback handler that does nothing
+    auto nullCallback =
+        [&notFoundCalled](const Request&,
+                          const std::shared_ptr<bmcweb::AsyncResp>&) {
+        notFoundCalled = true;
+    };
+
+    Router router;
+    std::error_code ec;
+
+    constexpr const std::string_view url = "/foo/bar";
+
+    Request req{{boost::beast::http::verb::get, url, 11}, ec};
+
+    router.newRuleTagged<getParameterTag(url)>("/foo/<path>")
+        .notFound()(nullCallback);
+    router.validate();
+    {
+        std::shared_ptr<bmcweb::AsyncResp> asyncResp =
+            std::make_shared<bmcweb::AsyncResp>();
+
+        router.handle(req, asyncResp);
+    }
+    EXPECT_TRUE(notFoundCalled);
 }
 } // namespace
-} // namespace crow
\ No newline at end of file
+} // namespace crow
diff --git a/redfish-core/lib/redfish_v1.hpp b/redfish-core/lib/redfish_v1.hpp
index a9a786d..6aa3ee6 100644
--- a/redfish-core/lib/redfish_v1.hpp
+++ b/redfish-core/lib/redfish_v1.hpp
@@ -137,7 +137,7 @@
 
     // Note, this route must always be registered last
     BMCWEB_ROUTE(app, "/redfish/<path>")
-    (std::bind_front(redfish404, std::ref(app)));
+        .notFound()(std::bind_front(redfish404, std::ref(app)));
 }
 
 } // namespace redfish
diff --git a/src/crow_getroutes_test.cpp b/src/crow_getroutes_test.cpp
index 58b745b..23a511e 100644
--- a/src/crow_getroutes_test.cpp
+++ b/src/crow_getroutes_test.cpp
@@ -68,4 +68,4 @@
                                      Pointee(Eq("/moo"))));
 }
 } // namespace
-} // namespace crow
\ No newline at end of file
+} // namespace crow