diff --git a/doc/release-notes.md b/doc/release-notes.md
--- a/doc/release-notes.md
+++ b/doc/release-notes.md
@@ -7,3 +7,6 @@
  - Remove the bip9_softforks result from the getblockchaininfo RPC call.
  - Remove the rules, vbavailable and vbrequired result from the getblocktemplate RPC call.
  - Remove the rules argument from the getblocktemplate RPC call.
+ - Update fee calculation to add 179 effective bytes per transaction output in excess of inputs.
+   Refund 179 bytes worth of minimum fee per input in excess of outputs to a minimum of
+   10 + 34 * (number of utxos)
diff --git a/src/primitives/transaction.h b/src/primitives/transaction.h
--- a/src/primitives/transaction.h
+++ b/src/primitives/transaction.h
@@ -312,6 +312,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 GetBillableSize() const;
+
     /**
      * Get the total transaction size in bytes.
      * @return Total transaction size in bytes
diff --git a/src/primitives/transaction.cpp b/src/primitives/transaction.cpp
--- a/src/primitives/transaction.cpp
+++ b/src/primitives/transaction.cpp
@@ -107,6 +107,24 @@
     return nTxSize;
 }
 
+size_t CTransaction::GetBillableSize() const {
+    size_t nTxSize = GetTotalSize(), inputs = vin.size(), outputs = vout.size();
+
+    // 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;
+}
+
 unsigned int CTransaction::GetTotalSize() const {
     return ::GetSerializeSize(*this, SER_NETWORK, PROTOCOL_VERSION);
 }
diff --git a/src/test/transaction_tests.cpp b/src/test/transaction_tests.cpp
--- a/src/test/transaction_tests.cpp
+++ b/src/test/transaction_tests.cpp
@@ -757,4 +757,24 @@
     BOOST_CHECK(!IsStandardTx(CTransaction(t), reason));
 }
 
+BOOST_AUTO_TEST_CASE(tx_transaction_fee) {
+    std::vector<size_t> sizes = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512};
+    for (size_t inputs : sizes) {
+        for (size_t outputs : sizes) {
+            CMutableTransaction mtx;
+            mtx.vin.resize(inputs);
+            mtx.vout.resize(outputs);
+            CTransaction tx(mtx);
+            auto txBillableSize = tx.GetBillableSize();
+            auto txSize = tx.GetTotalSize();
+            BOOST_CHECK(txBillableSize > 0);
+            if (inputs > outputs) {
+                BOOST_CHECK(txBillableSize < txSize);
+            } else {
+                BOOST_CHECK(txBillableSize >= txSize);
+            }
+        }
+    }
+}
+
 BOOST_AUTO_TEST_SUITE_END()
diff --git a/src/txmempool.h b/src/txmempool.h
--- a/src/txmempool.h
+++ b/src/txmempool.h
@@ -86,6 +86,8 @@
     Amount nFee;
     //!< ... and avoid recomputing tx size
     size_t nTxSize;
+    //!< ... and billable size for billing
+    size_t nTxBillableSize;
     //!< ... and modified size for priority
     size_t nModSize;
     //!< ... and total memory usage
@@ -143,6 +145,8 @@
     double GetPriority(unsigned int currentHeight) const;
     const Amount GetFee() const { return nFee; }
     size_t GetTxSize() const { return nTxSize; }
+    size_t GetTxBillableSize() const { return nTxBillableSize; }
+
     int64_t GetTime() const { return nTime; }
     unsigned int GetHeight() const { return entryHeight; }
     int64_t GetSigOpCount() const { return sigOpCount; }
diff --git a/src/txmempool.cpp b/src/txmempool.cpp
--- a/src/txmempool.cpp
+++ b/src/txmempool.cpp
@@ -32,6 +32,7 @@
       spendsCoinbase(_spendsCoinbase), sigOpCount(_sigOpsCount),
       lockPoints(lp) {
     nTxSize = tx->GetTotalSize();
+    nTxBillableSize = tx->GetBillableSize();
     nModSize = tx->CalculateModifiedSize(GetTxSize());
     nUsageSize = RecursiveDynamicUsage(tx);
 
@@ -894,7 +895,7 @@
 static TxMempoolInfo
 GetInfo(CTxMemPool::indexed_transaction_set::const_iterator it) {
     return TxMempoolInfo{it->GetSharedTx(), it->GetTime(),
-                         CFeeRate(it->GetFee(), it->GetTxSize()),
+                         CFeeRate(it->GetFee(), it->GetTxBillableSize()),
                          it->GetModifiedFee() - it->GetFee()};
 }
 
diff --git a/src/validation.cpp b/src/validation.cpp
--- a/src/validation.cpp
+++ b/src/validation.cpp
@@ -883,6 +883,7 @@
                               chainActive.Height(), inChainInputValue,
                               fSpendsCoinbase, nSigOpsCount, lp);
         unsigned int nSize = entry.GetTxSize();
+        size_t feeSize = tx.GetBillableSize();
 
         // Check that the transaction doesn't have an excessive number of
         // sigops, making it impossible to mine. Since the coinbase transaction
@@ -900,7 +901,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,
@@ -908,7 +909,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.
@@ -920,7 +921,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;
@@ -933,6 +934,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
@@ -2919,6 +2919,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.GetBillableSize();
+
             dPriority = txNewConst.ComputePriority(dPriority, nBytes);
 
             // Remove scriptSigs to eliminate the fee calculation dummy
@@ -2935,20 +2941,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.
-            Amount minFee = GetConfig().GetMinFeePerKB().GetFee(nBytes);
+            Amount minFee = GetConfig().GetMinFeePerKB().GetFee(feeBytes);
             if (nFeeNeeded < minFee) {
                 strFailReason = _("Transaction too large for fee policy");
                 return false;
diff --git a/test/functional/fundrawtransaction.py b/test/functional/fundrawtransaction.py
--- a/test/functional/fundrawtransaction.py
+++ b/test/functional/fundrawtransaction.py
@@ -151,7 +151,7 @@
 
         inputs = [{'txid': utx['txid'], 'vout': utx['vout']}]
         outputs = {
-            self.nodes[0].getnewaddress(): Decimal(5.0) - fee - feeTolerance}
+            self.nodes[0].getnewaddress(): satoshi_round(Decimal(5.0) - fee - feeTolerance)}
         rawtx = self.nodes[2].createrawtransaction(inputs, outputs)
         dec_tx = self.nodes[2].decoderawtransaction(rawtx)
         assert_equal(utx['txid'], dec_tx['vin'][0]['txid'])
diff --git a/test/functional/mempool_limit.py b/test/functional/mempool_limit.py
--- a/test/functional/mempool_limit.py
+++ b/test/functional/mempool_limit.py
@@ -21,7 +21,7 @@
         relayfee = self.nodes[0].getnetworkinfo()['relayfee']
 
         txids = []
-        utxos = create_confirmed_utxos(relayfee, self.nodes[0], 91)
+        utxos = create_confirmed_utxos(relayfee, self.nodes[0], 121)
 
         # create a mempool tx that will be evicted
         us0 = utxos.pop()
@@ -38,7 +38,7 @@
 
         relayfee = self.nodes[0].getnetworkinfo()['relayfee']
         base_fee = relayfee * 100
-        for i in range(3):
+        for i in range(4):
             txids.append([])
             txids[i] = create_lots_of_big_transactions(
                 self.nodes[0], txouts, utxos[30 * i:30 * i + 30], 30, (i + 1) * base_fee)
diff --git a/test/functional/test_framework/mininode.py b/test/functional/test_framework/mininode.py
--- a/test/functional/test_framework/mininode.py
+++ b/test/functional/test_framework/mininode.py
@@ -412,7 +412,8 @@
         for vout in self.vout:
             # Include the sizes for the outputs.
             tx_size += len(ToHex(vout))//2
-        return tx_size
+        tx_size += (len(self.vout) - len(self.vin))*179
+        return max(tx_size, 10 + 34 * len(self.vout))
 
     def serialize(self):
         r = b""
diff --git a/test/functional/test_framework/test_node.py b/test/functional/test_framework/test_node.py
--- a/test/functional/test_framework/test_node.py
+++ b/test/functional/test_framework/test_node.py
@@ -167,7 +167,7 @@
     def calculate_fee(self, tx):
         # Relay fee is in satoshis per KB.  Thus the 1000, and the COIN added
         # to get back to an amount of satoshis.
-        return int(self.relay_fee() / 1000 * len(ToHex(tx)) * COIN)
+        return int(self.relay_fee() / 1000 * tx.billable_size() * COIN)
 
     def calculate_fee_from_txid(self, txid):
         ctx = FromHex(CTransaction(), self.getrawtransaction(txid))
diff --git a/test/functional/wallet.py b/test/functional/wallet.py
--- a/test/functional/wallet.py
+++ b/test/functional/wallet.py
@@ -5,6 +5,9 @@
 """Test the wallet."""
 from test_framework.test_framework import BitcoinTestFramework
 from test_framework.util import *
+from test_framework.mininode import *
+
+import io
 
 
 class WalletTest(BitcoinTestFramework):
@@ -159,8 +162,9 @@
         txid = self.nodes[2].sendtoaddress(address, 10, "", "", False)
         self.nodes[2].generate(1)
         self.sync_all([self.nodes[0:3]])
+        ctx = FromHex(CTransaction(), self.nodes[2].getrawtransaction(txid))
         node_2_bal = self.check_fee_amount(self.nodes[2].getbalance(), Decimal(
-            '84'), fee_per_byte, count_bytes(self.nodes[2].getrawtransaction(txid)))
+            '84'), fee_per_byte, ctx.billable_size())
         assert_equal(self.nodes[0].getbalance(), Decimal('10'))
 
         # Send 10 BTC with subtract fee from amount
@@ -177,8 +181,9 @@
         self.nodes[2].generate(1)
         self.sync_all([self.nodes[0:3]])
         node_0_bal += Decimal('10')
+        ctx = FromHex(CTransaction(), self.nodes[2].getrawtransaction(txid))
         node_2_bal = self.check_fee_amount(self.nodes[2].getbalance(
-        ), node_2_bal - Decimal('10'), fee_per_byte, count_bytes(self.nodes[2].getrawtransaction(txid)))
+        ), node_2_bal - Decimal('10'), fee_per_byte, ctx.billable_size())
         assert_equal(self.nodes[0].getbalance(), node_0_bal)
 
         # Sendmany 10 BTC with subtract fee from amount
@@ -187,8 +192,9 @@
         self.sync_all([self.nodes[0:3]])
         node_2_bal -= Decimal('10')
         assert_equal(self.nodes[2].getbalance(), node_2_bal)
+        ctx = FromHex(CTransaction(), self.nodes[2].getrawtransaction(txid))
         node_0_bal = self.check_fee_amount(self.nodes[0].getbalance(
-        ), node_0_bal + Decimal('10'), fee_per_byte, count_bytes(self.nodes[2].getrawtransaction(txid)))
+        ), node_0_bal + Decimal('10'), fee_per_byte, ctx.billable_size())
 
         # Test ResendWalletTransactions:
         # Create a couple of transactions, then start up a fourth