diff --git a/src/test/mempool_tests.cpp b/src/test/mempool_tests.cpp
--- a/src/test/mempool_tests.cpp
+++ b/src/test/mempool_tests.cpp
@@ -919,16 +919,16 @@
         BOOST_CHECK(!compare(b, a));
     };
 
-    // If the fees and the time are the same, lower ID should sort before
+    // If the fees and entryId are the same, lower TxId should sort before
     checkOrdering(entry.Fee(100 * SATOSHI).FromTx(b),
                   entry.Fee(100 * SATOSHI).FromTx(a));
-    // Earlier time, same fee, should sort before
-    checkOrdering(entry.Fee(100 * SATOSHI).Time(1).FromTx(a),
-                  entry.Fee(100 * SATOSHI).Time(2).FromTx(b));
-    // Higher fee, earlier time should sort before
-    checkOrdering(entry.Fee(101 * SATOSHI).Time(1).FromTx(a),
-                  entry.Fee(100 * SATOSHI).Time(2).FromTx(b));
-    // Higher fee, same time should sort before
+    // Earlier entryId, same fee, should sort before
+    checkOrdering(entry.Fee(100 * SATOSHI).EntryId(1).FromTx(a),
+                  entry.Fee(100 * SATOSHI).EntryId(2).FromTx(b));
+    // Higher fee, earlier entryId should sort before
+    checkOrdering(entry.Fee(101 * SATOSHI).EntryId(1).FromTx(a),
+                  entry.Fee(100 * SATOSHI).EntryId(2).FromTx(b));
+    // Higher fee, same entryId should sort before
     checkOrdering(entry.Fee(101 * SATOSHI).FromTx(a),
                   entry.Fee(100 * SATOSHI).FromTx(b));
 
@@ -940,9 +940,9 @@
         entryA.UpdateFeeDelta(100 * SATOSHI);
         checkOrdering(entryB, entryA);
     }
-    // .. A is first seen
-    CTxMemPoolEntry entryA = entry.Fee(100 * SATOSHI).Time(1).FromTx(a);
-    CTxMemPoolEntry entryB = entry.Fee(100 * SATOSHI).Time(2).FromTx(b);
+    // .. A is first entering the mempool
+    CTxMemPoolEntry entryA = entry.Fee(100 * SATOSHI).EntryId(1).FromTx(a);
+    CTxMemPoolEntry entryB = entry.Fee(100 * SATOSHI).EntryId(2).FromTx(b);
     checkOrdering(entryA, entryB);
     // .. B has higher modified fee.
     entryB.UpdateFeeDelta(1 * SATOSHI);
diff --git a/src/test/util/setup_common.h b/src/test/util/setup_common.h
--- a/src/test/util/setup_common.h
+++ b/src/test/util/setup_common.h
@@ -203,6 +203,7 @@
     unsigned int nHeight;
     bool spendsCoinbase;
     unsigned int nSigChecks;
+    uint64_t entryId = 0;
 
     TestMemPoolEntryHelper()
         : nFee(), nTime(0), nHeight(1), spendsCoinbase(false), nSigChecks(1) {}
@@ -231,6 +232,10 @@
         nSigChecks = _nSigChecks;
         return *this;
     }
+    TestMemPoolEntryHelper &EntryId(uint64_t _entryId) {
+        entryId = _entryId;
+        return *this;
+    }
 };
 
 enum class ScriptError;
diff --git a/src/test/util/setup_common.cpp b/src/test/util/setup_common.cpp
--- a/src/test/util/setup_common.cpp
+++ b/src/test/util/setup_common.cpp
@@ -401,8 +401,10 @@
 
 CTxMemPoolEntry
 TestMemPoolEntryHelper::FromTx(const CTransactionRef &tx) const {
-    return CTxMemPoolEntry(tx, nFee, nTime, nHeight, spendsCoinbase, nSigChecks,
-                           LockPoints());
+    CTxMemPoolEntry ret(tx, nFee, nTime, nHeight, spendsCoinbase, nSigChecks,
+                        LockPoints());
+    ret.SetEntryId(entryId);
+    return ret;
 }
 
 /**
diff --git a/src/txmempool.h b/src/txmempool.h
--- a/src/txmempool.h
+++ b/src/txmempool.h
@@ -245,12 +245,14 @@
             return frA > frB;
         }
 
-        // Then by whichever was seen first
-        if (a.GetTime() != b.GetTime()) {
-            return a.GetTime() < b.GetTime();
+        // Ties are broken by whichever is topologically earlier
+        // (this helps mining code avoid some backtracking).
+        if (a.GetEntryId() != b.GetEntryId()) {
+            return a.GetEntryId() < b.GetEntryId();
         }
 
-        // If nothing else, sort by txid
+        // If nothing else, sort by txid (this should never happen as entryID is
+        // expected to be unique).
         return a.GetSharedTx()->GetId() < b.GetSharedTx()->GetId();
     }
 };