diff --git a/src/wallet/wallet.cpp b/src/wallet/wallet.cpp
--- a/src/wallet/wallet.cpp
+++ b/src/wallet/wallet.cpp
@@ -2869,47 +2869,8 @@
         std::vector<COutput> vAvailableCoins;
         AvailableCoins(vAvailableCoins, true, coinControl);
 
-        // Create change script that will be used if we need change
-        // TODO: pass in scriptChange instead of reservekey so
-        // change transaction isn't always pay-to-bitcoin-address
-        CScript scriptChange;
-
-        // coin control: send change to custom address
-        if (coinControl &&
-            !boost::get<CNoDestination>(&coinControl->destChange)) {
-            scriptChange = GetScriptForDestination(coinControl->destChange);
-
-            // no coin control: send change to newly generated address
-        } else {
-            // Note: We use a new key here to keep it from being obvious
-            // which side is the change.
-            //  The drawback is that by not reusing a previous key, the
-            //  change may be lost if a backup is restored, if the backup
-            //  doesn't have the new private key for the change. If we
-            //  reused the old key, it would be possible to add code to look
-            //  for and rediscover unknown transactions that were written
-            //  with keys of ours to recover post-backup change.
-
-            // Reserve a new key pair from key pool
-            CPubKey vchPubKey;
-            bool ret;
-            ret = reservekey.GetReservedKey(vchPubKey, true);
-            if (!ret) {
-                strFailReason =
-                    _("Keypool ran out, please call keypoolrefill first");
-                return false;
-            }
-
-            scriptChange = GetScriptForDestination(vchPubKey.GetID());
-        }
-        CTxOut change_prototype_txout(Amount::zero(), scriptChange);
-        size_t change_prototype_size =
-            GetSerializeSize(change_prototype_txout, SER_DISK, 0);
-
         nFeeRet = Amount::zero();
-        bool pick_new_inputs = true;
-        Amount nValueIn = Amount::zero();
-        // Start with no fee and loop until there is enough fee
+        // Start with no fee and loop until there is enough fee.
         while (true) {
             nChangePosInOut = nChangePosRequest;
             txNew.vin.clear();
@@ -2960,15 +2921,13 @@
                 txNew.vout.push_back(txout);
             }
 
-            // Choose coins to use
-            if (pick_new_inputs) {
-                nValueIn = Amount::zero();
-                setCoins.clear();
-                if (!SelectCoins(vAvailableCoins, nValueToSelect, setCoins,
-                                 nValueIn, coinControl)) {
-                    strFailReason = _("Insufficient funds");
-                    return false;
-                }
+            // Choose coins to use.
+            Amount nValueIn = Amount::zero();
+            setCoins.clear();
+            if (!SelectCoins(vAvailableCoins, nValueToSelect, setCoins,
+                             nValueIn, coinControl)) {
+                strFailReason = _("Insufficient funds");
+                return false;
             }
 
             for (const auto &pcoin : setCoins) {
@@ -2990,6 +2949,40 @@
             const Amount nChange = nValueIn - nValueToSelect;
             if (nChange > Amount::zero()) {
                 // Fill a vout to ourself.
+                // TODO: pass in scriptChange instead of reservekey so change
+                // transaction isn't always pay-to-bitcoin-address.
+                CScript scriptChange;
+
+                // Coin control: send change to custom address.
+                if (coinControl &&
+                    !boost::get<CNoDestination>(&coinControl->destChange)) {
+                    scriptChange =
+                        GetScriptForDestination(coinControl->destChange);
+
+                    // No coin control: send change to newly generated address.
+                } else {
+                    // Note: We use a new key here to keep it from being obvious
+                    // which side is the change. The drawback is that by not
+                    // reusing a previous key, the change may be lost if a
+                    // backup is restored, if the backup doesn't have the new
+                    // private key for the change. If we reused the old key, it
+                    // would be possible to add code to look for and rediscover
+                    // unknown transactions that were written with keys of ours
+                    // to recover post-backup change.
+
+                    // Reserve a new key pair from key pool.
+                    CPubKey vchPubKey;
+                    bool ret;
+                    ret = reservekey.GetReservedKey(vchPubKey, true);
+                    if (!ret) {
+                        strFailReason = _("Keypool ran out, please call "
+                                          "keypoolrefill first");
+                        return false;
+                    }
+
+                    scriptChange = GetScriptForDestination(vchPubKey.GetID());
+                }
+
                 CTxOut newTxOut(nChange, scriptChange);
 
                 // We do not move dust-change to fees, because the sender would
@@ -3024,6 +3017,7 @@
                 if (newTxOut.IsDust(dustRelayFee)) {
                     nChangePosInOut = -1;
                     nFeeRet += nChange;
+                    reservekey.ReturnKey();
                 } else {
                     if (nChangePosInOut == -1) {
                         // Insert change txn at random position:
@@ -3039,6 +3033,7 @@
                     txNew.vout.insert(position, newTxOut);
                 }
             } else {
+                reservekey.ReturnKey();
                 nChangePosInOut = -1;
             }
 
@@ -3091,36 +3086,15 @@
             }
 
             if (nFeeRet >= nFeeNeeded) {
-                // Reduce fee to only the needed amount if possible. This
-                // prevents potential overpayment in fees if the coins selected
-                // to meet nFeeNeeded result in a transaction that requires less
-                // fee than the prior iteration.
-
+                // Reduce fee to only the needed amount if we have change output
+                // to increase. This prevents potential overpayment in fees if
+                // the coins selected to meet nFeeNeeded result in a transaction
+                // that requires less fee than the prior iteration.
                 // TODO: The case where nSubtractFeeFromAmount > 0 remains to be
                 // addressed because it requires returning the fee to the payees
                 // and not the change output.
-
-                // If we have no change and a big enough excess fee, then try to
-                // construct transaction again only without picking new inputs.
-                // We now know we only need the smaller fee (because of reduced
-                // tx size) and so we should add a change output. Only try this
-                // once.
-                Amount fee_needed_for_change =
-                    GetMinimumFee(change_prototype_size,
-                                  currentConfirmationTarget, g_mempool);
-                Amount minimum_value_for_change =
-                    change_prototype_txout.GetDustThreshold(dustRelayFee);
-                Amount max_excess_fee =
-                    fee_needed_for_change + minimum_value_for_change;
-                if (nFeeRet > nFeeNeeded + max_excess_fee &&
-                    nChangePosInOut == -1 && nSubtractFeeFromAmount == 0 &&
-                    pick_new_inputs) {
-                    pick_new_inputs = false;
-                    nFeeRet = nFeeNeeded + fee_needed_for_change;
-                    continue;
-                }
-
-                // If we have change output already, just increase it
+                // TODO: The case where there is no change output remains to be
+                // addressed so we avoid creating too small an output.
                 if (nFeeRet > nFeeNeeded && nChangePosInOut != -1 &&
                     nSubtractFeeFromAmount == 0) {
                     Amount extraFeePaid = nFeeRet - nFeeNeeded;
@@ -3132,12 +3106,6 @@
 
                 // Done, enough fee included.
                 break;
-            } else if (!pick_new_inputs) {
-                // This shouldn't happen, we should have had enough excess fee
-                // to pay for the new output and still meet nFeeNeeded
-                strFailReason =
-                    _("Transaction fee and change calculation failed");
-                return false;
             }
 
             // Try to reduce change to include necessary fee.
@@ -3161,11 +3129,6 @@
             continue;
         }
 
-        if (nChangePosInOut == -1) {
-            // Return any reserved key if we don't have change
-            reservekey.ReturnKey();
-        }
-
         if (sign) {
             SigHashType sigHashType = SigHashType().withForkId();