diff --git a/northd/en-northd.c b/northd/en-northd.c
index 4479b4aff..badc49d43 100644
--- a/northd/en-northd.c
+++ b/northd/en-northd.c
@@ -259,3 +259,40 @@ en_northd_clear_tracked_data(void *data_)
     struct northd_data *data = data_;
     destroy_northd_data_tracked_changes(data);
 }
+
+bool
+sb_fdb_change_handler(struct engine_node *node, void *data)
+{
+    struct northd_data *nd = data;
+    const struct sbrec_fdb_table *sbrec_fdb_table =
+        EN_OVSDB_GET(engine_get_input("SB_fdb", node));
+
+    /* check if changed rows are stale and delete them */
+    const struct sbrec_fdb *fdb_e, *fdb_prev_del = NULL;
+    SBREC_FDB_TABLE_FOR_EACH_TRACKED(fdb_e, sbrec_fdb_table) {
+        if (sbrec_fdb_is_deleted(fdb_e)) {
+            continue;
+        }
+
+        if (fdb_prev_del) {
+            sbrec_fdb_delete(fdb_prev_del);
+        }
+
+        fdb_prev_del = fdb_e;
+        struct ovn_datapath *od
+            = ovn_datapath_find_by_key(&nd->ls_datapaths.datapaths,
+                                          fdb_e->dp_key);
+        if (od) {
+            if (ovn_tnlid_present(&od->port_tnlids, fdb_e->port_key)) {
+                fdb_prev_del = NULL;
+            }
+        }
+    }
+
+    if (fdb_prev_del) {
+        sbrec_fdb_delete(fdb_prev_del);
+    }
+
+    engine_set_node_state(node, EN_UPDATED);
+    return true;
+}
diff --git a/northd/en-northd.h b/northd/en-northd.h
index 9b7bda32a..9c722e401 100644
--- a/northd/en-northd.h
+++ b/northd/en-northd.h
@@ -19,5 +19,6 @@ bool northd_nb_logical_switch_handler(struct engine_node *, void *data);
 bool northd_nb_logical_router_handler(struct engine_node *, void *data);
 bool northd_sb_port_binding_handler(struct engine_node *, void *data);
 bool northd_lb_data_handler(struct engine_node *, void *data);
+bool sb_fdb_change_handler(struct engine_node *node, void *data);
 
 #endif /* EN_NORTHD_H */
diff --git a/northd/inc-proc-northd.c b/northd/inc-proc-northd.c
index d56e9783a..213e6d88a 100644
--- a/northd/inc-proc-northd.c
+++ b/northd/inc-proc-northd.c
@@ -189,7 +189,7 @@ void inc_proc_northd_init(struct ovsdb_idl_loop *nb,
     engine_add_input(&en_northd, &en_sb_ha_chassis_group, NULL);
     engine_add_input(&en_northd, &en_sb_ip_multicast, NULL);
     engine_add_input(&en_northd, &en_sb_service_monitor, NULL);
-    engine_add_input(&en_northd, &en_sb_fdb, NULL);
+    engine_add_input(&en_northd, &en_sb_fdb, sb_fdb_change_handler);
     engine_add_input(&en_northd, &en_sb_static_mac_binding, NULL);
     engine_add_input(&en_northd, &en_sb_chassis_template_var, NULL);
     engine_add_input(&en_northd, &en_global_config,
diff --git a/northd/northd.c b/northd/northd.c
index 6898daa00..8ad3ad285 100644
--- a/northd/northd.c
+++ b/northd/northd.c
@@ -496,7 +496,7 @@ ovn_datapath_find(const struct hmap *datapaths,
     return ovn_datapath_find_(datapaths, uuid);
 }
 
-static struct ovn_datapath *
+struct ovn_datapath *
 ovn_datapath_find_by_key(struct hmap *datapaths, uint32_t dp_key)
 {
     struct ovn_datapath *od;
@@ -3300,13 +3300,12 @@ delete_fdb_entry(struct ovsdb_idl_index *sbrec_fdb_by_dp_and_port,
     sbrec_fdb_index_set_dp_key(target, dp_key);
     sbrec_fdb_index_set_port_key(target, port_key);
 
-    struct sbrec_fdb *fdb_e = sbrec_fdb_index_find(sbrec_fdb_by_dp_and_port,
-                                                   target);
-    sbrec_fdb_index_destroy_row(target);
-
-    if (fdb_e) {
+    struct sbrec_fdb *fdb_e;
+    while ((fdb_e = sbrec_fdb_index_find(sbrec_fdb_by_dp_and_port,
+                                           target))) {
         sbrec_fdb_delete(fdb_e);
     }
+    sbrec_fdb_index_destroy_row(target);
 }
 
 struct service_monitor_info {
diff --git a/northd/northd.h b/northd/northd.h
index d4a8d75ab..26fe24df3 100644
--- a/northd/northd.h
+++ b/northd/northd.h
@@ -87,6 +87,9 @@ ods_size(const struct ovn_datapaths *datapaths)
     return hmap_count(&datapaths->datapaths);
 }
 
+struct ovn_datapath *
+ovn_datapath_find_by_key(struct hmap *datapaths, uint32_t dp_key);
+
 bool od_has_lb_vip(const struct ovn_datapath *od);
 
 struct tracked_ovn_ports {
