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
+    int 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 coinBlocksDestroyed / nTxSize;
 }
 
+int 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
@@ -775,6 +775,7 @@
 
         Amount nValueOut = tx.GetValueOut();
         Amount nFees = nValueIn - nValueOut;
+        int netOutputs = tx.GetNetOutputs();
         // nModifiedFees includes any fee deltas from PrioritiseTransaction
         Amount nModifiedFees = nFees;
         double nPriorityDummy = 0;
@@ -784,6 +785,10 @@
             view.GetChainValidTxInputValue(tx, chainActive.Height());
         double cbd = view.GetCoinBlocksDestroyed(tx, chainActive.Height());
         double dPriority = tx.ComputePriority(cbd);
+        // Find the average blocks destroyed in this transaction
+        double blocksDestroyed = txValidInputValue > Amount(0)
+                                     ? cbd / txValidInputValue.GetSatoshis()
+                                     : 0;
 
         // Keep track of transactions that spend a coinbase, which we re-scan
         // during reorgs to ensure COINBASE_MATURITY is still met.
@@ -801,6 +806,33 @@
                               fSpendsCoinbase, nSigOpsCount, lp);
         unsigned int nSize = entry.GetTxSize();
 
+        // Charge for net outputs, minus one change output
+        int netOutputsNoChange = netOutputs > 0 ? netOutputs - 1 : netOutputs;
+        Amount minUTXOfee =
+            std::max(Amount(0),
+                     ::minRelayTxFee.GetFee(nSize) +
+                         netOutputsNoChange * ::excessUTXOCharge);
+
+        // Start charging for extra UTXOs if:
+        //   1. mempool is filling up
+        //   2. the average number of blocks destroyed in this transaction is
+        //   less than 1
+        //   3. the tx is creating an excessive number of utxos
+
+        // TODO:
+        //   1. coinblocks configurable, make excessive utxo amount configurable
+        //   2. Rip these conditions out into another function that can be short
+        //      circuited if an appropriate fee is being met including a subsidy
+        //      for sweeping.
+
+        if (mempool.DynamicMemoryUsage() > config.GetMaxBlockSize() * 2 &&
+            blocksDestroyed < 1.0 && netOutputsNoChange > 10 &&
+            nModifiedFees < minUTXOfee) {
+            return state.DoS(0, false, REJECT_INSUFFICIENTFEE,
+                             "mempool min utxo creation fee not met", false,
+                             strprintf("%d < %d", nModifiedFees, minUTXOfee));
+        }
+
         // 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