diff --git a/doc/release-notes.md b/doc/release-notes.md
--- a/doc/release-notes.md
+++ b/doc/release-notes.md
@@ -12,3 +12,10 @@
 followed by `generatetoaddress`, can generate blocks for command line testing
 purposes. This is a client-side version of the former `generate` RPC. See
 the help for details.
+
+## Notification changes
+
+`-walletnotify` notifications are now sent for wallet transactions that are
+removed from the mempool because they conflict with a new block. These
+notifications were sent previously before the v0.21.13 release, but had been
+broken since that release.
diff --git a/src/interfaces/chain.h b/src/interfaces/chain.h
--- a/src/interfaces/chain.h
+++ b/src/interfaces/chain.h
@@ -25,6 +25,8 @@
 class CScheduler;
 class TxValidationState;
 
+enum class MemPoolRemovalReason;
+
 struct BlockHash;
 struct bilingual_str;
 struct CBlockLocator;
@@ -271,8 +273,9 @@
     public:
         virtual ~Notifications() {}
         virtual void transactionAddedToMempool(const CTransactionRef &tx) {}
-        virtual void transactionRemovedFromMempool(const CTransactionRef &ptx) {
-        }
+        virtual void
+        transactionRemovedFromMempool(const CTransactionRef &ptx,
+                                      MemPoolRemovalReason reason) {}
         virtual void blockConnected(const CBlock &block, int height) {}
         virtual void blockDisconnected(const CBlock &block, int height) {}
         virtual void updatedBlockTip() {}
diff --git a/src/interfaces/chain.cpp b/src/interfaces/chain.cpp
--- a/src/interfaces/chain.cpp
+++ b/src/interfaces/chain.cpp
@@ -75,8 +75,10 @@
         void TransactionAddedToMempool(const CTransactionRef &tx) override {
             m_notifications->transactionAddedToMempool(tx);
         }
-        void TransactionRemovedFromMempool(const CTransactionRef &tx) override {
-            m_notifications->transactionRemovedFromMempool(tx);
+        void
+        TransactionRemovedFromMempool(const CTransactionRef &tx,
+                                      MemPoolRemovalReason reason) override {
+            m_notifications->transactionRemovedFromMempool(tx, reason);
         }
         void BlockConnected(const std::shared_ptr<const CBlock> &block,
                             const CBlockIndex *index) override {
diff --git a/src/txmempool.cpp b/src/txmempool.cpp
--- a/src/txmempool.cpp
+++ b/src/txmempool.cpp
@@ -469,7 +469,8 @@
         // for any reason except being included in a block. Clients interested
         // in transactions included in blocks can subscribe to the
         // BlockConnected notification.
-        GetMainSignals().TransactionRemovedFromMempool(it->GetSharedTx());
+        GetMainSignals().TransactionRemovedFromMempool(it->GetSharedTx(),
+                                                       reason);
     }
 
     for (const CTxIn &txin : it->GetTx().vin) {
diff --git a/src/validationinterface.h b/src/validationinterface.h
--- a/src/validationinterface.h
+++ b/src/validationinterface.h
@@ -21,6 +21,7 @@
 class CValidationInterface;
 class uint256;
 class CScheduler;
+enum class MemPoolRemovalReason;
 
 /** Register subscriber */
 void RegisterValidationInterface(CValidationInterface *callbacks);
@@ -137,7 +138,8 @@
      *
      * Called on a background thread.
      */
-    virtual void TransactionRemovedFromMempool(const CTransactionRef &ptx) {}
+    virtual void TransactionRemovedFromMempool(const CTransactionRef &ptx,
+                                               MemPoolRemovalReason reason) {}
     /**
      * Notifies listeners of a block being connected.
      * Provides a vector of transactions evicted from the mempool as a result.
@@ -218,7 +220,8 @@
     void UpdatedBlockTip(const CBlockIndex *, const CBlockIndex *,
                          bool fInitialDownload);
     void TransactionAddedToMempool(const CTransactionRef &);
-    void TransactionRemovedFromMempool(const CTransactionRef &);
+    void TransactionRemovedFromMempool(const CTransactionRef &,
+                                       MemPoolRemovalReason);
     void BlockConnected(const std::shared_ptr<const CBlock> &,
                         const CBlockIndex *pindex);
     void BlockDisconnected(const std::shared_ptr<const CBlock> &,
diff --git a/src/validationinterface.cpp b/src/validationinterface.cpp
--- a/src/validationinterface.cpp
+++ b/src/validationinterface.cpp
@@ -213,10 +213,11 @@
                           ptx->GetHash().ToString());
 }
 
-void CMainSignals::TransactionRemovedFromMempool(const CTransactionRef &ptx) {
-    auto event = [ptx, this] {
+void CMainSignals::TransactionRemovedFromMempool(const CTransactionRef &ptx,
+                                                 MemPoolRemovalReason reason) {
+    auto event = [ptx, reason, this] {
         m_internals->Iterate([&](CValidationInterface &callbacks) {
-            callbacks.TransactionRemovedFromMempool(ptx);
+            callbacks.TransactionRemovedFromMempool(ptx, reason);
         });
     };
     ENQUEUE_AND_LOG_EVENT(event, "%s: txid=%s", __func__,
diff --git a/src/wallet/wallet.h b/src/wallet/wallet.h
--- a/src/wallet/wallet.h
+++ b/src/wallet/wallet.h
@@ -1086,7 +1086,8 @@
                                          std::optional<int> max_height,
                                          const WalletRescanReserver &reserver,
                                          bool fUpdate);
-    void transactionRemovedFromMempool(const CTransactionRef &ptx) override;
+    void transactionRemovedFromMempool(const CTransactionRef &ptx,
+                                       MemPoolRemovalReason reason) override;
     void ReacceptWalletTransactions() EXCLUSIVE_LOCKS_REQUIRED(cs_wallet);
     void ResendWalletTransactions();
     struct Balance {
diff --git a/src/wallet/wallet.cpp b/src/wallet/wallet.cpp
--- a/src/wallet/wallet.cpp
+++ b/src/wallet/wallet.cpp
@@ -23,6 +23,7 @@
 #include <script/sighashtype.h>
 #include <script/sign.h>
 #include <script/signingprovider.h>
+#include <txmempool.h>
 #include <util/bip32.h>
 #include <util/check.h>
 #include <util/error.h>
@@ -1225,12 +1226,45 @@
     }
 }
 
-void CWallet::transactionRemovedFromMempool(const CTransactionRef &ptx) {
+void CWallet::transactionRemovedFromMempool(const CTransactionRef &ptx,
+                                            MemPoolRemovalReason reason) {
     LOCK(cs_wallet);
     auto it = mapWallet.find(ptx->GetId());
     if (it != mapWallet.end()) {
         it->second.fInMempool = false;
     }
+    // Handle transactions that were removed from the mempool because they
+    // conflict with transactions in a newly connected block.
+    if (reason == MemPoolRemovalReason::CONFLICT) {
+        // Call SyncNotifications, so external -walletnotify notifications will
+        // be triggered for these transactions. Set Status::UNCONFIRMED instead
+        // of Status::CONFLICTED for a few reasons:
+        //
+        // 1. The transactionRemovedFromMempool callback does not currently
+        //    provide the conflicting block's hash and height, and for backwards
+        //    compatibility reasons it may not be not safe to store conflicted
+        //    wallet transactions with a null block hash. See
+        //    https://github.com/bitcoin/bitcoin/pull/18600#discussion_r420195993.
+        // 2. For most of these transactions, the wallet's internal conflict
+        //    detection in the blockConnected handler will subsequently call
+        //    MarkConflicted and update them with CONFLICTED status anyway. This
+        //    applies to any wallet transaction that has inputs spent in the
+        //    block, or that has ancestors in the wallet with inputs spent by
+        //    the block.
+        // 3. Longstanding behavior since the sync implementation in
+        //    https://github.com/bitcoin/bitcoin/pull/9371 and the prior sync
+        //    implementation before that was to mark these transactions
+        //    unconfirmed rather than conflicted.
+        //
+        // Nothing described above should be seen as an unchangeable requirement
+        // when improving this code in the future. The wallet's heuristics for
+        // distinguishing between conflicted and unconfirmed transactions are
+        // imperfect, and could be improved in general, see
+        // https://github.com/bitcoin-core/bitcoin-devwiki/wiki/Wallet-Transaction-Conflict-Tracking
+        SyncTransaction(ptx,
+                        {CWalletTx::Status::UNCONFIRMED, /* block height  */ 0,
+                         BlockHash(), /* index */ 0});
+    }
 }
 
 void CWallet::blockConnected(const CBlock &block, int height) {
@@ -1243,7 +1277,8 @@
         CWalletTx::Confirmation confirm(CWalletTx::Status::CONFIRMED, height,
                                         block_hash, index);
         SyncTransaction(block.vtx[index], confirm);
-        transactionRemovedFromMempool(block.vtx[index]);
+        transactionRemovedFromMempool(block.vtx[index],
+                                      MemPoolRemovalReason::BLOCK);
     }
 }
 
diff --git a/test/functional/feature_notifications.py b/test/functional/feature_notifications.py
--- a/test/functional/feature_notifications.py
+++ b/test/functional/feature_notifications.py
@@ -13,6 +13,7 @@
     connect_nodes,
     disconnect_nodes,
     wait_until,
+    disconnect_nodes,
     hex_str_to_bytes,
 )