diff --git a/controller/binding.c b/controller/binding.c
index 8ac2ce3e2..0712d7030 100644
--- a/controller/binding.c
+++ b/controller/binding.c
@@ -3126,8 +3126,17 @@ delete_done:
             update_ld_peers(pb, b_ctx_out->local_datapaths);
         }
 
-        handled = handle_updated_port(b_ctx_in, b_ctx_out, pb);
-        if (!handled) {
+        if (!handle_updated_port(b_ctx_in, b_ctx_out, pb)) {
+            handled = false;
+            break;
+        }
+
+        if (!sbrec_port_binding_is_new(pb) &&
+            sbrec_port_binding_is_updated(pb,
+                                          SBREC_PORT_BINDING_COL_TUNNEL_KEY) &&
+            get_local_datapath(b_ctx_out->local_datapaths,
+                               pb->datapath->tunnel_key)) {
+            handled = false;
             break;
         }
     }
diff --git a/controller/ovn-controller.c b/controller/ovn-controller.c
index 23269af83..356ce881a 100644
--- a/controller/ovn-controller.c
+++ b/controller/ovn-controller.c
@@ -1894,7 +1894,6 @@ runtime_data_sb_datapath_binding_handler(struct engine_node *node OVS_UNUSED,
             engine_get_input("SB_datapath_binding", node));
     const struct sbrec_datapath_binding *dp;
     struct ed_type_runtime_data *rt_data = data;
-    struct local_datapath *ld;
 
     SBREC_DATAPATH_BINDING_TABLE_FOR_EACH_TRACKED (dp, dp_table) {
         if (sbrec_datapath_binding_is_deleted(dp)) {
@@ -1902,27 +1901,19 @@ runtime_data_sb_datapath_binding_handler(struct engine_node *node OVS_UNUSED,
                                    dp->tunnel_key)) {
                 return false;
             }
+
+        }
+
+        if (sbrec_datapath_binding_is_updated(
+                dp, SBREC_DATAPATH_BINDING_COL_TUNNEL_KEY) &&
+            !sbrec_datapath_binding_is_new(dp)) {
             /* If the tunnel key got updated, get_local_datapath will not find
              * the ld. Use get_local_datapath_no_hash which does not
              * rely on the hash.
              */
-            if (sbrec_datapath_binding_is_updated(
-                    dp, SBREC_DATAPATH_BINDING_COL_TUNNEL_KEY)) {
-                if (get_local_datapath_no_hash(&rt_data->local_datapaths,
-                                               dp->tunnel_key)) {
-                    return false;
-                }
-            }
-        } else if (sbrec_datapath_binding_is_updated(
-                        dp, SBREC_DATAPATH_BINDING_COL_TUNNEL_KEY)
-                   && !sbrec_datapath_binding_is_new(dp)) {
-            /* If the tunnel key is updated, remove the entry (with a wrong
-             * hash) from the map. It will be (properly) added back later.
-             */
-            if ((ld = get_local_datapath_no_hash(&rt_data->local_datapaths,
-                                                 dp->tunnel_key))) {
-                hmap_remove(&rt_data->local_datapaths, &ld->hmap_node);
-                local_datapath_destroy(ld);
+            if (get_local_datapath_no_hash(&rt_data->local_datapaths,
+                                           dp->tunnel_key)) {
+                return false;
             }
         }
     }
diff --git a/northd/northd.c b/northd/northd.c
index 133cddb69..0cabda7ea 100644
--- a/northd/northd.c
+++ b/northd/northd.c
@@ -4550,6 +4550,8 @@ ls_handle_lsp_changes(struct ovsdb_idl_txn *ovnsb_idl_txn,
                 op->visited = true;
                 continue;
             }
+
+            uint32_t old_tunnel_key = op->tunnel_key;
             if (!ls_port_reinit(op, ovnsb_idl_txn,
                                 new_nbsp,
                                 od, sb, ni->sbrec_mirror_table,
@@ -4563,6 +4565,11 @@ ls_handle_lsp_changes(struct ovsdb_idl_txn *ovnsb_idl_txn,
                 goto fail;
             }
             add_op_to_northd_tracked_ports(&trk_lsps->updated, op);
+
+            if (old_tunnel_key != op->tunnel_key) {
+                delete_fdb_entry(ni->sbrec_fdb_by_dp_and_port, od->tunnel_key,
+                                 old_tunnel_key);
+            }
         }
         op->visited = true;
     }
diff --git a/tests/ovn.at b/tests/ovn.at
index 79c9524c6..784b3dd1f 100644
--- a/tests/ovn.at
+++ b/tests/ovn.at
@@ -37472,6 +37472,8 @@ sim_add hv1
 as hv1
 check ovs-vsctl add-br br-phys
 ovn_attach n1 br-phys 192.168.0.11
+ovs-vsctl -- add-port br-int vif1 -- \
+    set interface vif1 external-ids:iface-id=lsp1
 
 check ovn-nbctl --wait=hv ls-add ls \
           -- lsp-add ls lsp1 \
@@ -37484,6 +37486,56 @@ check ovn-nbctl --wait=hv ls-add ls \
                addresses=router \
           -- lrp-set-gateway-chassis lr-ls hv1
 
+dp_uuid=$(fetch_column datapath _uuid external_ids:name=lr)
+ovn-sbctl create MAC_Binding ip=192.168.1.10 datapath=$dp_uuid logical_port=lr-ls mac='"00:00:00:00:00:01"'
+
+OVN_POPULATE_ARP
+wait_for_ports_up
+check ovn-nbctl --wait=hv sync
+
+create_fdb() {
+    ls_key=$(fetch_column datapath tunnel_key external_ids:name=ls)
+    lsp_key=$(fetch_column port_binding tunnel_key logical_port=lsp1)
+
+    ovn-sbctl create FDB mac='"00:00:00:00:00:01"' dp_key=$ls_key port_key=$lsp_key
+}
+
+AS_BOX([Logical switch tunnel_key change])
+create_fdb
+
+check ovn-nbctl --wait=hv set Logical_Switch ls other_config:requested-tnl-key=10
+ovn-sbctl list datapath
+CHECK_FLOWS_AFTER_RECOMPUTE([hv1], [hv1])
+
+check_row_count FDB 0 mac='"00:00:00:00:00:01"'
+
+AS_BOX([Logical switch port tunnel_key change])
+create_fdb
+
+check ovn-nbctl --wait=hv set Logical_Switch_Port lsp1 options:requested-tnl-key=10
+CHECK_FLOWS_AFTER_RECOMPUTE([hv1], [hv1])
+
+check_row_count FDB 0 mac='"00:00:00:00:00:01"'
+
+AS_BOX([Logical router tunnel_key change])
+check ovn-nbctl --wait=hv set Logical_Router lr options:requested-tnl-key=20
+CHECK_FLOWS_AFTER_RECOMPUTE([hv1], [hv1])
+
+check_row_count Mac_Binding 1 ip=192.168.1.10
+AT_CHECK([ovs-ofctl dump-flows br-int table=OFTABLE_MAC_LOOKUP | grep -c metadata=0x14], [0], [dnl
+1
+])
+
+AS_BOX([Logical router port tunnel_key change])
+check ovn-nbctl --wait=hv set Logical_Router_Port lr-ls options:requested-tnl-key=20
+CHECK_FLOWS_AFTER_RECOMPUTE([hv1], [hv1])
+
+check_row_count Mac_Binding 1 ip=192.168.1.10
+AT_CHECK([ovs-ofctl dump-flows br-int table=OFTABLE_MAC_LOOKUP | grep -c reg14=0x14], [0], [dnl
+1
+])
+
+AS_BOX([Logical switch tunnel_key change, potential segfault])
 sleep_controller hv1
 
 check ovn-nbctl --wait=sb set Logical_Switch ls other_config:requested-tnl-key=1000
