diff --git a/src/validation.cpp b/src/validation.cpp
--- a/src/validation.cpp
+++ b/src/validation.cpp
@@ -757,17 +757,37 @@
         return PackageMempoolAcceptResult(package_state, {});
     }
 
+    // Construct workspaces and check package policies.
     std::vector<Workspace> workspaces{};
     workspaces.reserve(package_count);
-    std::transform(txns.cbegin(), txns.cend(), std::back_inserter(workspaces),
-                   [&args, this](const auto &tx) {
-                       return Workspace(
-                           tx,
-                           GetNextBlockScriptFlags(
-                               args.m_config.GetChainParams().GetConsensus(),
-                               m_active_chainstate.m_chain.Tip()));
-                   });
-
+    {
+        std::unordered_set<TxId, SaltedTxIdHasher> later_txids;
+        std::transform(txns.cbegin(), txns.cend(),
+                       std::inserter(later_txids, later_txids.end()),
+                       [](const auto &tx) { return tx->GetId(); });
+        // Require the package to be sorted in order of dependency, i.e.
+        // parents appear before children.
+        // An unsorted package will fail anyway on missing-inputs, but it's
+        // better to quit earlier and fail on something less ambiguous
+        // (missing-inputs could also be an orphan or trying to spend
+        // nonexistent coins).
+        for (const auto &tx : txns) {
+            for (const auto &input : tx->vin) {
+                if (later_txids.find(input.prevout.GetTxId()) !=
+                    later_txids.end()) {
+                    // The parent is a subsequent transaction in the package.
+                    package_state.Invalid(PackageValidationResult::PCKG_POLICY,
+                                          "package-not-sorted");
+                    return PackageMempoolAcceptResult(package_state, {});
+                }
+            }
+            later_txids.erase(tx->GetId());
+            workspaces.emplace_back(
+                tx, GetNextBlockScriptFlags(
+                        args.m_config.GetChainParams().GetConsensus(),
+                        m_active_chainstate.m_chain.Tip()));
+        }
+    }
     std::map<const TxId, const MempoolAcceptResult> results;
     {
         // Don't allow any conflicting transactions, i.e. spending the same
diff --git a/test/functional/rpc_packages.py b/test/functional/rpc_packages.py
--- a/test/functional/rpc_packages.py
+++ b/test/functional/rpc_packages.py
@@ -190,12 +190,10 @@
 
         self.log.info(
             "Check that testmempoolaccept requires packages to be sorted by dependency")
-        testres_multiple_unsorted = node.testmempoolaccept(
-            rawtxs=chain_hex[::-1])
-        assert_equal(testres_multiple_unsorted,
-                     [{"txid": chain_txns[-1].get_id(), "allowed": False,
-                       "reject-reason": "missing-inputs"}]
-                     + [{"txid": tx.get_id(), } for tx in chain_txns[::-1]][1:])
+        assert_equal(
+            node.testmempoolaccept(rawtxs=chain_hex[::-1]),
+            [{"txid": tx.get_id(), "package-error": "package-not-sorted"}
+             for tx in chain_txns[::-1]])
 
         self.log.info("Testmempoolaccept a chain of 50 transactions")
         testres_multiple = node.testmempoolaccept(rawtxs=chain_hex)