diff --git a/test/functional/bip68-sequence.py b/test/functional/bip68-sequence.py
--- a/test/functional/bip68-sequence.py
+++ b/test/functional/bip68-sequence.py
@@ -224,17 +224,25 @@
         tx1 = FromHex(CTransaction(), self.nodes[0].getrawtransaction(txid))
         tx1.rehash()
 
+        # As the fees are calculated prior to the transaction being signed,
+        # there is some uncertainty that calculate fee provides the correct
+        # minimal fee. Since regtest coins are free, let's go ahead and
+        # increase the fee by an order of magnitude to ensure this test
+        # passes.
+        fee_multiplier = 10
+
         # Anyone-can-spend mempool tx.
         # Sequence lock of 0 should pass.
         tx2 = CTransaction()
         tx2.nVersion = 2
         tx2.vin = [CTxIn(COutPoint(tx1.sha256, 0), nSequence=0)]
         tx2.vout = [
-            CTxOut(int(tx1.vout[0].nValue - self.relayfee * COIN), CScript([b'a']))]
+            CTxOut(int(0), CScript([b'a']))]
+        tx2.vout[0].nValue = tx1.vout[0].nValue - \
+            fee_multiplier * self.nodes[0].calculate_fee(tx2)
         tx2_raw = self.nodes[0].signrawtransaction(ToHex(tx2))["hex"]
         tx2 = FromHex(tx2, tx2_raw)
         tx2.rehash()
-
         self.nodes[0].sendrawtransaction(tx2_raw)
 
         # Create a spend of the 0th output of orig_tx with a sequence lock
@@ -250,7 +258,7 @@
             tx.vin = [
                 CTxIn(COutPoint(orig_tx.sha256, 0), nSequence=sequence_value)]
             tx.vout = [
-                CTxOut(int(orig_tx.vout[0].nValue - relayfee * COIN), CScript([b'a']))]
+                CTxOut(int(orig_tx.vout[0].nValue - fee_multiplier * self.nodes[0].calculate_fee(tx)), CScript([b'a']))]
             tx.rehash()
 
             if (orig_tx.hash in node.getrawmempool()):
@@ -271,7 +279,7 @@
         # Now mine some blocks, but make sure tx2 doesn't get mined.
         # Use prioritisetransaction to lower the effective feerate to 0
         self.nodes[0].prioritisetransaction(
-            tx2.hash, -1e15, int(-self.relayfee * COIN))
+            tx2.hash, -1e15, -fee_multiplier * self.nodes[0].calculate_fee(tx2))
         cur_time = int(time.time())
         for i in range(10):
             self.nodes[0].setmocktime(cur_time + 600)
@@ -287,7 +295,7 @@
 
         # Mine tx2, and then try again
         self.nodes[0].prioritisetransaction(
-            tx2.hash, 1e15, self.nodes[0].calculate_fee(tx2))
+            tx2.hash, 1e15, fee_multiplier * fee_multiplier*self.nodes[0].calculate_fee(tx2))
 
         # Advance the time on the node so that we can test timelocks
         self.nodes[0].setmocktime(cur_time + 600)
diff --git a/test/functional/test_framework/mininode.py b/test/functional/test_framework/mininode.py
--- a/test/functional/test_framework/mininode.py
+++ b/test/functional/test_framework/mininode.py
@@ -402,6 +402,18 @@
         self.sha256 = None
         self.hash = None
 
+    def billable_size(self):
+        # We need a heuristic for unsigned transactions as they do not yet
+        # include the pubkey hash, or the signature.
+        tx_size = 10  # base transaction overhead
+        for vin in self.vin:
+            # Max of sig + p2kh, or the actual size if it's more.
+            tx_size += max(len(ToHex(vin))//2, 147)
+        for vout in self.vout:
+            # Include the sizes for the outputs.
+            tx_size += len(ToHex(vout))//2
+        return tx_size
+
     def serialize(self):
         r = b""
         r += struct.pack("<i", self.nVersion)