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,23 +224,31 @@
         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
         # of 1, and test what happens when submitting.
         # orig_tx.vout[0] must be an anyone-can-spend output
-        def test_nonzero_locks(orig_tx, node, relayfee, use_height_lock):
+        def test_nonzero_locks(orig_tx, node, use_height_lock):
             sequence_value = 1
             if not use_height_lock:
                 sequence_value |= SEQUENCE_LOCKTIME_TYPE_FLAG
@@ -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 * node.calculate_fee(tx)), CScript([b'a']))]
             tx.rehash()
 
             if (orig_tx.hash in node.getrawmempool()):
@@ -264,14 +272,14 @@
             return tx
 
         test_nonzero_locks(
-            tx2, self.nodes[0], self.relayfee, use_height_lock=True)
+            tx2, self.nodes[0], use_height_lock=True)
         test_nonzero_locks(
-            tx2, self.nodes[0], self.relayfee, use_height_lock=False)
+            tx2, self.nodes[0], use_height_lock=False)
 
         # 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)
@@ -281,13 +289,13 @@
         assert(tx2.hash in self.nodes[0].getrawmempool())
 
         test_nonzero_locks(
-            tx2, self.nodes[0], self.relayfee, use_height_lock=True)
+            tx2, self.nodes[0], use_height_lock=True)
         test_nonzero_locks(
-            tx2, self.nodes[0], self.relayfee, use_height_lock=False)
+            tx2, self.nodes[0], use_height_lock=False)
 
         # Mine tx2, and then try again
         self.nodes[0].prioritisetransaction(
-            tx2.hash, 1e15, self.nodes[0].calculate_fee(tx2))
+            tx2.hash, 1e15, 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)
@@ -297,7 +305,7 @@
         # Now that tx2 is not in the mempool, a sequence locked spend should
         # succeed
         tx3 = test_nonzero_locks(
-            tx2, self.nodes[0], self.relayfee, use_height_lock=False)
+            tx2, self.nodes[0], use_height_lock=False)
         assert(tx3.hash in self.nodes[0].getrawmempool())
 
         self.nodes[0].generate(1)
@@ -305,12 +313,12 @@
 
         # One more test, this time using height locks
         tx4 = test_nonzero_locks(
-            tx3, self.nodes[0], self.relayfee, use_height_lock=True)
+            tx3, self.nodes[0], use_height_lock=True)
         assert(tx4.hash in self.nodes[0].getrawmempool())
 
         # Now try combining confirmed and unconfirmed inputs
         tx5 = test_nonzero_locks(
-            tx4, self.nodes[0], self.relayfee, use_height_lock=True)
+            tx4, self.nodes[0], use_height_lock=True)
         assert(tx5.hash not in self.nodes[0].getrawmempool())
 
         utxos = self.nodes[0].listunspent()