diff --git a/src/wallet/wallet.h b/src/wallet/wallet.h
--- a/src/wallet/wallet.h
+++ b/src/wallet/wallet.h
@@ -347,6 +347,9 @@
     std::string strFromAccount;
     //!< position in ordered transaction list
     int64_t nOrderPos;
+    std::multimap<int64_t,
+                  std::pair<CWalletTx *, CAccountingEntry *>>::const_iterator
+        m_it_wtxOrdered;
 
     // memory only
     mutable bool fDebitCached;
diff --git a/src/wallet/wallet.cpp b/src/wallet/wallet.cpp
--- a/src/wallet/wallet.cpp
+++ b/src/wallet/wallet.cpp
@@ -992,7 +992,8 @@
     if (fInsertedNew) {
         wtx.nTimeReceived = GetAdjustedTime();
         wtx.nOrderPos = IncOrderPosNext(&batch);
-        wtxOrdered.insert(std::make_pair(wtx.nOrderPos, TxPair(&wtx, nullptr)));
+        wtx.m_it_wtxOrdered = wtxOrdered.insert(
+            std::make_pair(wtx.nOrderPos, TxPair(&wtx, nullptr)));
         wtx.nTimeSmart = ComputeTimeSmart(wtx);
         AddToSpends(txid);
     }
@@ -1053,9 +1054,13 @@
 
 void CWallet::LoadToWallet(const CWalletTx &wtxIn) {
     const TxId &txid = wtxIn.GetId();
-    CWalletTx &wtx = mapWallet.emplace(txid, wtxIn).first->second;
+    const auto &ins = mapWallet.emplace(txid, wtxIn);
+    CWalletTx &wtx = ins.first->second;
     wtx.BindWallet(this);
-    wtxOrdered.insert(std::make_pair(wtx.nOrderPos, TxPair(&wtx, nullptr)));
+    if (/* insertion took place */ ins.second) {
+        wtx.m_it_wtxOrdered = wtxOrdered.insert(
+            std::make_pair(wtx.nOrderPos, TxPair(&wtx, nullptr)));
+    }
     AddToSpends(txid);
     for (const CTxIn &txin : wtx.tx->vin) {
         auto it = mapWallet.find(txin.prevout.GetTxId());
@@ -3486,7 +3491,9 @@
     DBErrors nZapSelectTxRet =
         WalletBatch(*database, "cr+").ZapSelectTx(txIdsIn, txIdsOut);
     for (const TxId &txid : txIdsOut) {
-        mapWallet.erase(txid);
+        const auto &it = mapWallet.find(txid);
+        wtxOrdered.erase(it->second.m_it_wtxOrdered);
+        mapWallet.erase(it);
     }
 
     if (nZapSelectTxRet == DBErrors::NEED_REWRITE) {