diff --git a/src/primitives/transaction.h b/src/primitives/transaction.h
--- a/src/primitives/transaction.h
+++ b/src/primitives/transaction.h
@@ -307,6 +307,9 @@
     double ComputePriority(double dPriorityInputs,
                            unsigned int nTxSize = 0) const;
 
+    // Compute the net number of outputs
+    int64_t GetNetOutputs() const;
+
     // Compute modified tx size for priority calculation (optionally given tx
     // size)
     unsigned int CalculateModifiedSize(unsigned int nTxSize = 0) const;
diff --git a/src/primitives/transaction.cpp b/src/primitives/transaction.cpp
--- a/src/primitives/transaction.cpp
+++ b/src/primitives/transaction.cpp
@@ -110,6 +110,10 @@
     return dPriorityInputs / nTxSize;
 }
 
+int64_t CTransaction::GetNetOutputs() const {
+    return vout.size() - vin.size();
+}
+
 unsigned int CTransaction::CalculateModifiedSize(unsigned int nTxSize) const {
     // In order to avoid disincentivizing cleaning up the UTXO set we don't
     // count the constant overhead for each txin and up to 110 bytes of
diff --git a/src/validation.cpp b/src/validation.cpp
--- a/src/validation.cpp
+++ b/src/validation.cpp
@@ -877,6 +877,11 @@
                               fSpendsCoinbase, nSigOpsCount, lp);
         unsigned int nSize = entry.GetTxSize();
 
+        Amount minAcceptableFee =
+            std::max(Amount(0),
+                     ::minRelayTxFee.GetFee(nSize) -
+                         tx.GetNetOutputs() * config.GetExcessUTXOCharge());
+
         // Check that the transaction doesn't have an excessive number of
         // sigops, making it impossible to mine. Since the coinbase transaction
         // itself can contain sigops MAX_STANDARD_TX_SIGOPS is less than
@@ -900,7 +905,7 @@
         }
 
         if (gArgs.GetBoolArg("-relaypriority", DEFAULT_RELAYPRIORITY) &&
-            nModifiedFees < ::minRelayTxFee.GetFee(nSize) &&
+            nModifiedFees < minAcceptableFee &&
             !AllowFree(entry.GetPriority(chainActive.Height() + 1))) {
             // Require that free transactions have sufficient priority to be
             // mined in the next block.