diff --git a/src/amount.h b/src/amount.h
--- a/src/amount.h
+++ b/src/amount.h
@@ -186,6 +186,12 @@
      * Return the fee in satoshis for the given size in bytes.
      */
     Amount GetFee(size_t nBytes) const;
+    /**
+     * Return the ceiling of a fee calculation in satoshis for the given size in
+     * bytes.
+     */
+    Amount GetFeeCeiling(size_t nBytes) const;
+
     /**
      * Return the fee in satoshis for a size of 1000 bytes
      */
diff --git a/src/amount.cpp b/src/amount.cpp
--- a/src/amount.cpp
+++ b/src/amount.cpp
@@ -24,11 +24,20 @@
     }
 }
 
-Amount CFeeRate::GetFee(size_t nBytes_) const {
+template <bool ceil>
+static Amount GetFee(size_t nBytes_, Amount nSatoshisPerK) {
     assert(nBytes_ <= uint64_t(std::numeric_limits<int64_t>::max()));
     int64_t nSize = int64_t(nBytes_);
 
-    Amount nFee = nSize * nSatoshisPerK / 1000;
+    // Ensure fee is rounded up when truncated if ceil is true.
+    Amount nFee(0);
+    if (ceil) {
+        nFee = Amount(nSize * nSatoshisPerK % 1000 > Amount(0)
+                          ? nSize * nSatoshisPerK / 1000 + Amount(1)
+                          : nSize * nSatoshisPerK / 1000);
+    } else {
+        nFee = nSize * nSatoshisPerK / 1000;
+    }
 
     if (nFee == Amount(0) && nSize != 0) {
         if (nSatoshisPerK > Amount(0)) {
@@ -42,6 +51,14 @@
     return nFee;
 }
 
+Amount CFeeRate::GetFee(size_t nBytes) const {
+    return ::GetFee<false>(nBytes, nSatoshisPerK);
+}
+
+Amount CFeeRate::GetFeeCeiling(size_t nBytes) const {
+    return ::GetFee<true>(nBytes, nSatoshisPerK);
+}
+
 std::string CFeeRate::ToString() const {
     return strprintf("%d.%08d %s/kB", nSatoshisPerK / COIN,
                      nSatoshisPerK % COIN, CURRENCY_UNIT);
diff --git a/src/test/feerate_tests.cpp b/src/test/feerate_tests.cpp
--- a/src/test/feerate_tests.cpp
+++ b/src/test/feerate_tests.cpp
@@ -56,6 +56,14 @@
     BOOST_CHECK_EQUAL(feeRate.GetFee(8), Amount(-1));
     BOOST_CHECK_EQUAL(feeRate.GetFee(9), Amount(-1));
 
+    // Check ceiling results
+    feeRate = CFeeRate(Amount(18));
+    // Truncates the result, if not integer
+    BOOST_CHECK_EQUAL(feeRate.GetFeeCeiling(0), Amount(0));
+    BOOST_CHECK_EQUAL(feeRate.GetFeeCeiling(100), Amount(2));
+    BOOST_CHECK_EQUAL(feeRate.GetFeeCeiling(200), Amount(4));
+    BOOST_CHECK_EQUAL(feeRate.GetFeeCeiling(1000), Amount(18));
+
     // Check full constructor
     // default value
     BOOST_CHECK(CFeeRate(Amount(-1), 1000) == CFeeRate(Amount(-1)));
diff --git a/src/wallet/wallet.cpp b/src/wallet/wallet.cpp
--- a/src/wallet/wallet.cpp
+++ b/src/wallet/wallet.cpp
@@ -2942,13 +2942,13 @@
             }
 
             if (coinControl && coinControl->fOverrideFeeRate) {
-                nFeeNeeded = coinControl->nFeeRate.GetFee(nBytes);
+                nFeeNeeded = coinControl->nFeeRate.GetFeeCeiling(nBytes);
             }
 
             // 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().GetFeeCeiling(nBytes);
             if (nFeeNeeded < minFee) {
                 strFailReason = _("Transaction too large for fee policy");
                 return false;