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.h b/src/validation.h
--- a/src/validation.h
+++ b/src/validation.h
@@ -56,9 +56,9 @@
 /** Default for DEFAULT_WHITELISTFORCERELAY. */
 static const bool DEFAULT_WHITELISTFORCERELAY = true;
 /** Default for -minrelaytxfee, minimum relay fee for transactions */
-static const Amount DEFAULT_MIN_RELAY_TX_FEE(1000);
+static const Amount DEFAULT_MIN_RELAY_TX_FEE(690);
 /** Default for -excessutxocharge for transactions transactions */
-static const Amount DEFAULT_UTXO_FEE(0);
+static const Amount DEFAULT_UTXO_FEE(150);
 //! -maxtxfee default
 static const Amount DEFAULT_TRANSACTION_MAXFEE(COIN / 10);
 //! Discourage users to set fees higher than this amount (in satoshis) per kB
diff --git a/src/validation.cpp b/src/validation.cpp
--- a/src/validation.cpp
+++ b/src/validation.cpp
@@ -898,6 +898,26 @@
                               chainActive.Height(), inChainInputValue,
                               fSpendsCoinbase, nSigOpsCount, lp);
         unsigned int nSize = entry.GetTxSize();
+        int64_t netUTXOs = tx.GetNetOutputs();
+
+        Amount minAcceptableFee = ::minRelayTxFee.GetFee(nSize);
+
+        // Here we charge a small fee for the creation of UTXOs
+        // And provide a small rebate for consolidating old UTXOs
+        if (netUTXOs >= 0) {
+            // Charge a fee that should be approximately the cost of an
+            // input + output pair when a new UTXO is created.  The assumption
+            // is that an input is roughly 3 * the size of an output s
+            minAcceptableFee += netUTXOs * config.GetExcessUTXOCharge();
+        } else {
+            // Give a discount back for the approximate amount of space an input
+            // would take in the transaction.
+            // That is to say 75 of the UTXO charge.
+            minAcceptableFee -= 3 * netUTXOs * config.GetExcessUTXOCharge() / 4;
+        }
+
+        // Ensure the fee is above zero.
+        minAcceptableFee = std::max(Amount(0), minAcceptableFee);
 
         // Check that the transaction doesn't have an excessive number of
         // sigops, making it impossible to mine. Since the coinbase transaction
@@ -922,7 +942,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.