diff --git a/src/primitives/transaction.h b/src/primitives/transaction.h
--- a/src/primitives/transaction.h
+++ b/src/primitives/transaction.h
@@ -311,6 +311,10 @@
     // size)
     unsigned int CalculateModifiedSize(unsigned int nTxSize = 0) const;
 
+    // Computes an adjusted tx size so that the UTXIs are billed partially
+    // upfront.
+    size_t CalculateFeeSize() const;
+
     /**
      * Get the total transaction size in bytes.
      * @return Total transaction size in bytes
@@ -332,6 +336,12 @@
     std::string ToString() const;
 };
 
+/**
+* Calculates a modified size for a hypothetical transaction with a certain
+* base size, and number of inputs and outputs.
+*/
+size_t CalculateFeeSize(size_t nTxSize, size_t inputs, size_t outputs);
+
 /**
  * A mutable version of CTransaction.
  */
@@ -359,8 +369,10 @@
     }
 
     /**
-     * Compute the id and hash of this CMutableTransaction. This is computed on
-     * the fly, as opposed to GetId() and GetHash() in CTransaction, which uses
+     * Compute the id and hash of this CMutableTransaction. This is computed
+     * on
+     * the fly, as opposed to GetId() and GetHash() in CTransaction, which
+     * uses
      * a cached result.
      */
     TxId GetId() const;
diff --git a/src/primitives/transaction.cpp b/src/primitives/transaction.cpp
--- a/src/primitives/transaction.cpp
+++ b/src/primitives/transaction.cpp
@@ -127,6 +127,26 @@
     return nTxSize;
 }
 
+size_t CalculateFeeSize(size_t nTxSize, size_t inputs, size_t outputs) {
+    // 179 bytes is the minimum size it would take to spend any outputs which
+    // are created.  We want to change in advance of spending them to
+    // incentivize keeping your UTXO set reasonbly sized.
+    int64_t modSize =
+        int64_t(nTxSize) + (int64_t(outputs) - int64_t(inputs)) * 179;
+
+    // Note: It is impossible to generate a negative number above in any real
+    // world situation.  This is because the inputs have a least 179 byte
+    // each. However, it is possible to have shorter scriptSigs than 179
+    // bytes.  Therefore, we include a minimum of 10 bytes + 34 * vouts.
+    nTxSize = std::max(int64_t(outputs * 34 + 10), modSize);
+
+    return nTxSize;
+}
+
+size_t CTransaction::CalculateFeeSize() const {
+    return ::CalculateFeeSize(GetTotalSize(), vin.size(), vout.size());
+}
+
 unsigned int CTransaction::GetTotalSize() const {
     return ::GetSerializeSize(*this, SER_NETWORK, PROTOCOL_VERSION);
 }
diff --git a/src/validation.cpp b/src/validation.cpp
--- a/src/validation.cpp
+++ b/src/validation.cpp
@@ -898,6 +898,7 @@
                               chainActive.Height(), inChainInputValue,
                               fSpendsCoinbase, nSigOpsCount, lp);
         unsigned int nSize = entry.GetTxSize();
+        size_t feeSize = tx.CalculateFeeSize();
 
         // Check that the transaction doesn't have an excessive number of
         // sigops, making it impossible to mine. Since the coinbase transaction
@@ -914,7 +915,7 @@
             pool.GetMinFee(
                     gArgs.GetArg("-maxmempool", DEFAULT_MAX_MEMPOOL_SIZE) *
                     1000000)
-                .GetFee(nSize);
+                .GetFee(feeSize);
         if (mempoolRejectFee > Amount(0) && nModifiedFees < mempoolRejectFee) {
             return state.DoS(0, false, REJECT_INSUFFICIENTFEE,
                              "mempool min fee not met", false,
@@ -922,7 +923,7 @@
         }
 
         if (gArgs.GetBoolArg("-relaypriority", DEFAULT_RELAYPRIORITY) &&
-            nModifiedFees < ::minRelayTxFee.GetFee(nSize) &&
+            nModifiedFees < ::minRelayTxFee.GetFee(feeSize) &&
             !AllowFree(entry.GetPriority(chainActive.Height() + 1))) {
             // Require that free transactions have sufficient priority to be
             // mined in the next block.
@@ -934,7 +935,7 @@
         // This mitigates 'penny-flooding' -- sending thousands of free
         // transactions just to be annoying or make others' transactions take
         // longer to confirm.
-        if (fLimitFree && nModifiedFees < ::minRelayTxFee.GetFee(nSize)) {
+        if (fLimitFree && nModifiedFees < ::minRelayTxFee.GetFee(feeSize)) {
             static CCriticalSection csFreeLimiter;
             static double dFreeCount;
             static int64_t nLastTime;
@@ -947,6 +948,9 @@
             nLastTime = nNow;
             // -limitfreerelay unit is thousand-bytes-per-minute
             // At default rate it would take over a month to fill 1GB
+
+            // NOTE: Use the actual size here, and not the fee size since this
+            // is counting real size for the rate limiter.
             if (dFreeCount + nSize >=
                 gArgs.GetArg("-limitfreerelay", DEFAULT_LIMITFREERELAY) * 10 *
                     1000) {
diff --git a/src/wallet/wallet.cpp b/src/wallet/wallet.cpp
--- a/src/wallet/wallet.cpp
+++ b/src/wallet/wallet.cpp
@@ -2916,6 +2916,12 @@
 
             CTransaction txNewConst(txNew);
             unsigned int nBytes = txNewConst.GetTotalSize();
+
+            // Note: The relaying code has been changed to charge upfront for
+            // the  minimum required bytes to spend a UTXO.  This means that
+            // we need to calculate possible fees based that size.
+            size_t feeBytes = txNewConst.CalculateFeeSize();
+
             dPriority = txNewConst.ComputePriority(dPriority, nBytes);
 
             // Remove scriptSigs to eliminate the fee calculation dummy
@@ -2932,20 +2938,20 @@
             }
 
             Amount nFeeNeeded =
-                GetMinimumFee(nBytes, currentConfirmationTarget, mempool);
+                GetMinimumFee(feeBytes, currentConfirmationTarget, mempool);
             if (coinControl && nFeeNeeded > Amount(0) &&
                 coinControl->nMinimumTotalFee > nFeeNeeded) {
                 nFeeNeeded = coinControl->nMinimumTotalFee;
             }
 
             if (coinControl && coinControl->fOverrideFeeRate) {
-                nFeeNeeded = coinControl->nFeeRate.GetFee(nBytes);
+                nFeeNeeded = coinControl->nFeeRate.GetFee(feeBytes);
             }
 
             // If we made it here and we aren't even able to meet the relay fee
             // on the next pass, give up because we must be at the maximum
             // allowed fee.
-            if (nFeeNeeded < ::minRelayTxFee.GetFee(nBytes)) {
+            if (nFeeNeeded < ::minRelayTxFee.GetFee(feeBytes)) {
                 strFailReason = _("Transaction too large for fee policy");
                 return false;
             }