diff --git a/lib/ovn-util.c b/lib/ovn-util.c
index b6471063ef..8f6719471d 100644
--- a/lib/ovn-util.c
+++ b/lib/ovn-util.c
@@ -580,18 +580,30 @@ ovn_destroy_tnlids(struct hmap *tnlids)
     hmap_destroy(tnlids);
 }
 
+/* Returns true if 'tnlid' is present in the hmap 'tnlids'. */
 bool
-ovn_add_tnlid(struct hmap *set, uint32_t tnlid)
+ovn_tnlid_present(struct hmap *tnlids, uint32_t tnlid)
 {
     uint32_t hash = hash_int(tnlid, 0);
     struct tnlid_node *node;
-    HMAP_FOR_EACH_IN_BUCKET (node, hmap_node, hash, set) {
+    HMAP_FOR_EACH_IN_BUCKET (node, hmap_node, hash, tnlids) {
         if (node->tnlid == tnlid) {
-            return false;
+            return true;
         }
     }
 
-    node = xmalloc(sizeof *node);
+    return false;
+}
+
+bool
+ovn_add_tnlid(struct hmap *set, uint32_t tnlid)
+{
+    if (ovn_tnlid_present(set, tnlid)) {
+        return false;
+    }
+
+    uint32_t hash = hash_int(tnlid, 0);
+    struct tnlid_node *node = xmalloc(sizeof *node);
     hmap_insert(set, &node->hmap_node, hash);
     node->tnlid = tnlid;
     return true;
diff --git a/lib/ovn-util.h b/lib/ovn-util.h
index df4b0bc989..40ecafe57e 100644
--- a/lib/ovn-util.h
+++ b/lib/ovn-util.h
@@ -126,6 +126,7 @@ void ovn_conn_show(struct unixctl_conn *conn, int argc OVS_UNUSED,
 struct hmap;
 void ovn_destroy_tnlids(struct hmap *tnlids);
 bool ovn_add_tnlid(struct hmap *set, uint32_t tnlid);
+bool ovn_tnlid_present(struct hmap *tnlids, uint32_t tnlid);
 uint32_t ovn_allocate_tnlid(struct hmap *set, const char *name, uint32_t min,
                             uint32_t max, uint32_t *hint);
 
diff --git a/northd/ovn-northd.c b/northd/ovn-northd.c
index 23c26de36f..7b6f86802a 100644
--- a/northd/ovn-northd.c
+++ b/northd/ovn-northd.c
@@ -851,6 +851,20 @@ ovn_datapath_find(struct hmap *datapaths, const struct uuid *uuid)
     return NULL;
 }
 
+static struct ovn_datapath *
+ovn_datapath_find_by_key(struct hmap *datapaths, uint32_t dp_key)
+{
+    struct ovn_datapath *od;
+
+    HMAP_FOR_EACH (od, key_node, datapaths) {
+        if (od->tunnel_key == dp_key) {
+            return od;
+        }
+    }
+
+    return NULL;
+}
+
 static bool
 ovn_datapath_is_stale(const struct ovn_datapath *od)
 {
@@ -3144,6 +3158,26 @@ cleanup_sb_ha_chassis_groups(struct northd_context *ctx,
     }
 }
 
+static void
+cleanup_stale_fdp_entries(struct northd_context *ctx, struct hmap *datapaths)
+{
+    const struct sbrec_fdb *fdb_e, *next;
+    SBREC_FDB_FOR_EACH_SAFE (fdb_e, next, ctx->ovnsb_idl) {
+        bool delete = true;
+        struct ovn_datapath *od
+            = ovn_datapath_find_by_key(datapaths, fdb_e->dp_key);
+        if (od) {
+            if (ovn_tnlid_present(&od->port_tnlids, fdb_e->port_key)) {
+                delete = false;
+            }
+        }
+
+        if (delete) {
+            sbrec_fdb_delete(fdb_e);
+        }
+    }
+}
+
 struct service_monitor_info {
     struct hmap_node hmap_node;
     const struct sbrec_service_monitor *sbrec_mon;
@@ -12714,6 +12748,7 @@ ovnnb_db_run(struct northd_context *ctx,
     sync_port_groups(ctx, &port_groups);
     sync_meters(ctx, datapaths, &meter_groups, &port_groups);
     sync_dns_entries(ctx, datapaths);
+    cleanup_stale_fdp_entries(ctx, datapaths);
 
     struct ovn_northd_lb *lb;
     HMAP_FOR_EACH_POP (lb, hmap_node, &lbs) {
@@ -13701,6 +13736,11 @@ main(int argc, char *argv[])
     ovsdb_idl_add_column(ovnsb_idl_loop.idl, &sbrec_bfd_col_disc);
     ovsdb_idl_add_column(ovnsb_idl_loop.idl, &sbrec_bfd_col_src_port);
 
+    ovsdb_idl_add_table(ovnsb_idl_loop.idl, &sbrec_table_fdb);
+    add_column_noalert(ovnsb_idl_loop.idl, &sbrec_fdb_col_mac);
+    add_column_noalert(ovnsb_idl_loop.idl, &sbrec_fdb_col_dp_key);
+    add_column_noalert(ovnsb_idl_loop.idl, &sbrec_fdb_col_port_key);
+
     struct ovsdb_idl_index *sbrec_chassis_by_name
         = chassis_index_create(ovnsb_idl_loop.idl);
 
diff --git a/tests/ovn-northd.at b/tests/ovn-northd.at
index 1b4160cfa0..76634043cc 100644
--- a/tests/ovn-northd.at
+++ b/tests/ovn-northd.at
@@ -2443,3 +2443,63 @@ check ovn-sbctl set chassis hv1 other_config:port-up-notif=true
 wait_row_count nb:Logical_Switch_Port 1 up=false name=lsp1
 
 AT_CLEANUP
+
+AT_SETUP([ovn -- FDB cleanup])
+
+ovn_start
+
+ovn-nbctl ls-add sw0
+ovn-nbctl lsp-add sw0 sw0-p1
+ovn-nbctl lsp-add sw0 sw0-p2
+ovn-nbctl lsp-add sw0 sw0-p3
+
+ovn-nbctl ls-add sw1
+ovn-nbctl lsp-add sw1 sw1-p1
+ovn-nbctl lsp-add sw1 sw1-p2
+ovn-nbctl --wait=sb lsp-add sw1 sw1-p3
+
+sw0_key=$(fetch_column datapath_binding tunnel_key external_ids:name=sw0)
+sw1_key=$(fetch_column datapath_binding tunnel_key external_ids:name=sw1)
+sw0p1_key=$(fetch_column port_binding tunnel_key logical_port=sw0-p1)
+sw0p2_key=$(fetch_column port_binding tunnel_key logical_port=sw0-p2)
+sw1p1_key=$(fetch_column port_binding tunnel_key logical_port=sw1-p1)
+
+ovn-sbctl create FDB mac="00\:00\:00\:00\:00\:01" dp_key=$sw0_key port_key=$sw0p1_key
+ovn-sbctl create FDB mac="00\:00\:00\:00\:00\:02" dp_key=$sw0_key port_key=$sw0p1_key
+ovn-sbctl create FDB mac="00\:00\:00\:00\:00\:03" dp_key=$sw0_key port_key=$sw0p2_key
+ovn-sbctl create FDB mac="00\:00\:00\:00\:01\:01" dp_key=$sw1_key port_key=$sw1p1_key
+ovn-sbctl create FDB mac="00\:00\:00\:00\:01\:02" dp_key=$sw1_key port_key=$sw1p1_key
+ovn-sbctl create FDB mac="00\:00\:00\:00\:01\:03" dp_key=$sw1_key port_key=$sw1p1_key
+
+wait_row_count FDB 6
+
+ovn-sbctl create fdb mac="00\:00\:00\:00\:01\:03" dp_key=$sw1_key port_key=10
+wait_row_count FDB 6
+ovn-sbctl create fdb mac="00\:00\:00\:00\:01\:03" dp_key=4 port_key=10
+wait_row_count FDB 6
+
+ovn-nbctl --wait=sb ls-del sw1
+wait_row_count FDB 3
+
+ovn-nbctl lsp-del sw0-p3
+wait_row_count FDB 3
+
+ovn-nbctl lsp-del sw0-p1
+wait_row_count FDB 1
+
+check_column '00:00:00:00:00:03' FDB mac
+ovn-sbctl list fdb
+
+check_column $sw0_key FDB dp_key
+check_column $sw0p2_key FDB port_key
+
+ovn-nbctl --wait=sb lsp-add sw0-p1
+wait_row_count FDB 1
+
+ovn-nbctl lsp-del sw0-p2
+ovn-nbctl lsp-add sw0-p2
+wait_row_count FDB 0
+
+ovn-sbctl list FDB
+
+AT_CLEANUP
