diff --git a/test/functional/mining_getblocktemplate_longpoll.py b/test/functional/mining_getblocktemplate_longpoll.py
--- a/test/functional/mining_getblocktemplate_longpoll.py
+++ b/test/functional/mining_getblocktemplate_longpoll.py
@@ -72,8 +72,10 @@
         thr = LongpollThread(self.nodes[0])
         thr.start()
         # generate a random transaction and submit it
+        min_relay_fee = self.nodes[0].getnetworkinfo()["relayfee"]
+        # min_relay_fee is fee per 1000 bytes, which should be more than enough.
         (txid, txhex, fee) = random_transaction(self.nodes,
-                                                Decimal("1.1"), Decimal("0.0"), Decimal("0.001"), 20)
+                                                Decimal("1.1"), min_relay_fee, Decimal("0.001"), 20)
         # after one minute, every 10 seconds the mempool is probed, so in 80
         # seconds it should have returned
         thr.join(60 + 20)