diff --git a/src/bin_codec/codec.ml b/src/bin_codec/codec.ml
index 4af4266cc56f3a0dc72bbdea09bac97b50901753..a4a06d9ad429e8f8aaf537f4e8e3c48c8ef8d5ee 100644
--- a/src/bin_codec/codec.ml
+++ b/src/bin_codec/codec.ml
@@ -25,6 +25,8 @@
 
 let () = Additional_registrations.force_linking ()
 
+(* FIXME: https://gitlab.com/tezos/tezos/-/issues/4025
+   Remove backwards compatible Tezos symlinks. *)
 let warn_if_argv0_name_not_octez () =
   let executable_name = Filename.basename Sys.argv.(0) in
   let prefix = "tezos-" in
@@ -39,7 +41,8 @@ let warn_if_argv0_name_not_octez () =
     in
     Format.eprintf
       "@[<v 2>@{<warning>@{<title>Warning@}@}@,\
-       The executable with name %s has been renamed to %s. The name %s is now@,\
+       The executable with name @{<kwd>%s@} has been renamed to @{<kwd>%s@}. \
+       The name @{<kwd>%s@} is now@,\
        deprecated, and it will be removed in a future release. Please update@,\
        your scripts to use the new name.@]@\n\
        @."
diff --git a/src/bin_node/main.ml b/src/bin_node/main.ml
index ae93f840ae53744d2a29043dfb6b995319a9e3e1..f95805aa614bce1a8feb78615db21e226d111c23 100644
--- a/src/bin_node/main.ml
+++ b/src/bin_node/main.ml
@@ -24,6 +24,8 @@
 (*                                                                           *)
 (*****************************************************************************)
 
+(* FIXME: https://gitlab.com/tezos/tezos/-/issues/4025
+   Remove backwards compatible Tezos symlinks. *)
 let warn_if_argv0_name_not_octez () =
   let executable_name = Filename.basename Sys.argv.(0) in
   let prefix = "tezos-" in
@@ -38,7 +40,8 @@ let warn_if_argv0_name_not_octez () =
     in
     Format.eprintf
       "@[<v 2>@{<warning>@{<title>Warning@}@}@,\
-       The executable with name %s has been renamed to %s. The name %s is now@,\
+       The executable with name @{<kwd>%s@} has been renamed to @{<kwd>%s@}. \
+       The name @{<kwd>%s@} is now@,\
        deprecated, and it will be removed in a future release. Please update@,\
        your scripts to use the new name.@]@\n\
        @."
diff --git a/src/bin_proxy_server/main_proxy_server.ml b/src/bin_proxy_server/main_proxy_server.ml
index 92a815734edee2feb7c9903ee604bc7f113724dc..b61fdccbb47ce5cba0ae3443363bf1fe7709df52 100644
--- a/src/bin_proxy_server/main_proxy_server.ml
+++ b/src/bin_proxy_server/main_proxy_server.ml
@@ -26,6 +26,8 @@
 open Cmdliner
 module Proxy_server_config = Tezos_proxy_server_config.Proxy_server_config
 
+(* FIXME: https://gitlab.com/tezos/tezos/-/issues/4025
+   Remove backwards compatible Tezos symlinks. *)
 let () =
   (* warn_if_argv0_name_not_octez *)
   let executable_name = Filename.basename Sys.argv.(0) in
@@ -41,7 +43,8 @@ let () =
     in
     Format.eprintf
       "@[<v 2>@{<warning>@{<title>Warning@}@}@,\
-       The executable with name %s has been renamed to %s. The name %s is now@,\
+       The executable with name @{<kwd>%s@} has been renamed to @{<kwd>%s@}. \
+       The name @{<kwd>%s@} is now@,\
        deprecated, and it will be removed in a future release. Please update@,\
        your scripts to use the new name.@]@\n\
        @."
diff --git a/src/bin_snoop/main_snoop.ml b/src/bin_snoop/main_snoop.ml
index 8b8ab0b1d72dc4c55db08ac8cfb2e2c0d4f1870d..c650e17da762cc3b7dc23c9528209b5c8e8a3c9f 100644
--- a/src/bin_snoop/main_snoop.ml
+++ b/src/bin_snoop/main_snoop.ml
@@ -23,6 +23,8 @@
 (*                                                                           *)
 (*****************************************************************************)
 
+(* FIXME: https://gitlab.com/tezos/tezos/-/issues/4025
+   Remove backwards compatible Tezos symlinks. *)
 let () =
   (* warn_if_argv0_name_not_octez *)
   let executable_name = Filename.basename Sys.argv.(0) in
@@ -38,7 +40,8 @@ let () =
     in
     Format.eprintf
       "@[<v 2>@{<warning>@{<title>Warning@}@}@,\
-       The executable with name %s has been renamed to %s. The name %s is now@,\
+       The executable with name @{<kwd>%s@} has been renamed to @{<kwd>%s@}. \
+       The name @{<kwd>%s@} is now@,\
        deprecated, and it will be removed in a future release. Please update@,\
        your scripts to use the new name.@]@\n\
        @."
diff --git a/src/bin_validation/bin/main_validator.ml b/src/bin_validation/bin/main_validator.ml
index c43a45fcd7b13ef44e5493fdfe97d20d3983d705..8d87aacbbadef2bf449e54dfd89a0afce7fb86c2 100644
--- a/src/bin_validation/bin/main_validator.ml
+++ b/src/bin_validation/bin/main_validator.ml
@@ -23,6 +23,8 @@
 (*                                                                           *)
 (*****************************************************************************)
 
+(* FIXME: https://gitlab.com/tezos/tezos/-/issues/4025
+   Remove backwards compatible Tezos symlinks. *)
 let () =
   (* warn_if_argv0_name_not_octez *)
   let executable_name = Filename.basename Sys.argv.(0) in
@@ -38,7 +40,8 @@ let () =
     in
     Format.eprintf
       "@[<v 2>@{<warning>@{<title>Warning@}@}@,\
-       The executable with name %s has been renamed to %s. The name %s is now@,\
+       The executable with name @{<kwd>%s@} has been renamed to @{<kwd>%s@}. \
+       The name @{<kwd>%s@} is now@,\
        deprecated, and it will be removed in a future release. Please update@,\
        your scripts to use the new name.@]@\n\
        @."
diff --git a/src/lib_client_base_unix/client_main_run.ml b/src/lib_client_base_unix/client_main_run.ml
index 2fd4c5a4beaf52709155b6b5b8dd05be96c4b06b..3b8e12d2510df6a56434ce6871a24f3921868b15 100644
--- a/src/lib_client_base_unix/client_main_run.ml
+++ b/src/lib_client_base_unix/client_main_run.ml
@@ -317,35 +317,71 @@ let setup_client_config (cctxt : Tezos_client_base.Client_context.printer)
           setup_non_mockup_rpc_client_config m
       | `Mode_mockup -> setup_mockup_rpc_client_config cctxt args base_dir)
 
+(* FIXME: https://gitlab.com/tezos/tezos/-/issues/4025
+   Remove backwards compatible Tezos symlinks. *)
 let warn_if_argv0_name_not_octez () =
-  let keep_version_number = true in
-  let executable_name = Filename.basename Sys.argv.(0) in
-  let expected_name =
-    match TzString.split '-' executable_name with
-    | prefix :: (("endorser" | "accuser" | "baker") as bin) :: arg :: rest ->
-        let has_version_number = int_of_string_opt arg <> None in
-        if String.equal prefix "tezos" || has_version_number then
-          if has_version_number then
-            if keep_version_number then
-              Some (String.concat "-" ("octez" :: bin :: arg :: rest))
-            else Some (String.concat "-" ("octez" :: bin :: rest))
-          else Some (String.concat "-" ("octez" :: bin :: arg :: rest))
-        else None
-    | "tezos" :: rest -> Some (String.concat "-" ("octez" :: rest))
-    | _ -> None
+  let executable_name =
+    (* example: tezos-tx-rollup-client-015-PtKathma *)
+    Filename.basename Sys.argv.(0)
   in
-  let expected_name =
-    Option.bind expected_name (fun expected_name ->
-        if String.equal executable_name expected_name then None
-        else Some expected_name)
-  in
-  match expected_name with
-  | None -> ()
-  | Some expected_name ->
+  let old_head = "tezos-" in
+  let new_head = "octez-" in
+  match TzString.has_prefix executable_name ~prefix:old_head with
+  | false -> ()
+  | true ->
+      let expected_name =
+        let len_prefix = String.length old_head in
+        let headless_name =
+          (* example: tx-rollup-client-015-PtKathma *)
+          String.sub
+            executable_name
+            len_prefix
+            (String.length executable_name - len_prefix)
+        in
+        let name_without_version name =
+          match headless_name |> String.starts_with ~prefix:name with
+          | false -> None
+          | true ->
+              let len_name = String.length name in
+              let version_proto =
+                (* example: -015-PtKathma *)
+                String.sub
+                  headless_name
+                  len_name
+                  (String.length headless_name - len_name)
+              in
+              let num_hyphens =
+                (* example: 2 *)
+                version_proto
+                |> String.fold_left
+                     (fun acc c -> match c with '-' -> acc + 1 | _ -> acc)
+                     0
+              in
+              let proto =
+                (* example: -PtKathma *)
+                if num_hyphens = 2 then
+                  String.sub version_proto 4 (String.length version_proto - 4)
+                else version_proto
+              in
+              Some (name ^ proto)
+        in
+        (* example: tx-rollup-client-PtKathma *)
+        let versionless_name =
+          ["accuser"; "baker"; "tx-rollup-client"; "tx-rollup-node"]
+          |> List.map name_without_version
+          |> List.find Option.is_some |> Option.join
+        in
+        (* example: octez-tx-rollup-client-PtKathma *)
+        new_head
+        ^
+        match versionless_name with
+        | None -> headless_name
+        | Some versionless_name -> versionless_name
+      in
       Format.eprintf
         "@[<v 2>@{<warning>@{<title>Warning@}@}@,\
-         The executable with name %s has been renamed to %s. The name %s is \
-         now@,\
+         The executable with name @{<kwd>%s@} has been renamed to @{<kwd>%s@}. \
+         The name @{<kwd>%s@} is now@,\
          deprecated, and it will be removed in a future release. Please update@,\
          your scripts to use the new name.@]@\n\
          @."
diff --git a/src/lib_protocol_compiler/bin/main_embedded_packer.ml b/src/lib_protocol_compiler/bin/main_embedded_packer.ml
index 2fee9d6bceafb664b2ae48559233610640ddb8f0..6d80cfb27beca73a141b8187b45db57d98901528 100644
--- a/src/lib_protocol_compiler/bin/main_embedded_packer.ml
+++ b/src/lib_protocol_compiler/bin/main_embedded_packer.ml
@@ -23,6 +23,8 @@
 (*                                                                           *)
 (*****************************************************************************)
 
+(* FIXME: https://gitlab.com/tezos/tezos/-/issues/4025
+   Remove backwards compatible Tezos symlinks. *)
 let () =
   (* warn_if_argv0_name_not_octez *)
   let executable_name = Filename.basename Sys.argv.(0) in
@@ -38,7 +40,8 @@ let () =
     in
     Format.eprintf
       "@[<v 2>@{<warning>@{<title>Warning@}@}@,\
-       The executable with name %s has been renamed to %s. The name %s is now@,\
+       The executable with name @{<kwd>%s@} has been renamed to @{<kwd>%s@}. \
+       The name @{<kwd>%s@} is now@,\
        deprecated, and it will be removed in a future release. Please update@,\
        your scripts to use the new name.@]@\n\
        @."
diff --git a/src/lib_protocol_compiler/bin/main_native.ml b/src/lib_protocol_compiler/bin/main_native.ml
index c5e0a418352b60becffbed6e4bc4b89ed883add3..36a479c9d8945772e33015ccd00816a67640deb5 100644
--- a/src/lib_protocol_compiler/bin/main_native.ml
+++ b/src/lib_protocol_compiler/bin/main_native.ml
@@ -23,6 +23,8 @@
 (*                                                                           *)
 (*****************************************************************************)
 
+(* FIXME: https://gitlab.com/tezos/tezos/-/issues/4025
+   Remove backwards compatible Tezos symlinks. *)
 let () =
   (* warn_if_argv0_name_not_octez *)
   let executable_name = Filename.basename Sys.argv.(0) in
@@ -39,7 +41,8 @@ let () =
     in
     Format.eprintf
       "@[<v 2>@{<warning>@{<title>Warning@}@}@,\
-       The executable with name %s has been renamed to %s. The name %s is now@,\
+       The executable with name @{<kwd>%s@} has been renamed to @{<kwd>%s@}. \
+       The name @{<kwd>%s@} is now@,\
        deprecated, and it will be removed in a future release. Please update@,\
        your scripts to use the new name.@]@\n\
        @."
diff --git a/src/lib_protocol_compiler/bin/main_packer.ml b/src/lib_protocol_compiler/bin/main_packer.ml
index f168881eb000908287063e88439b66104c95b168..e053856832c1083efa6f90941e74e88caff6c889 100644
--- a/src/lib_protocol_compiler/bin/main_packer.ml
+++ b/src/lib_protocol_compiler/bin/main_packer.ml
@@ -25,6 +25,8 @@
 
 open Filename.Infix
 
+(* FIXME: https://gitlab.com/tezos/tezos/-/issues/4025
+   Remove backwards compatible Tezos symlinks. *)
 let () =
   (* warn_if_argv0_name_not_octez *)
   let executable_name = Filename.basename Sys.argv.(0) in
@@ -40,7 +42,8 @@ let () =
     in
     Format.eprintf
       "@[<v 2>@{<warning>@{<title>Warning@}@}@,\
-       The executable with name %s has been renamed to %s. The name %s is now@,\
+       The executable with name @{<kwd>%s@} has been renamed to @{<kwd>%s@}. \
+       The name @{<kwd>%s@} is now@,\
        deprecated, and it will be removed in a future release. Please update@,\
        your scripts to use the new name.@]@\n\
        @."
diff --git a/src/proto_014_PtKathma/bin_tx_rollup_client/main_tx_rollup_client_014_PtKathma.ml b/src/proto_014_PtKathma/bin_tx_rollup_client/main_tx_rollup_client_014_PtKathma.ml
index bb6b4fba9684be61a1a976ba7e37cfbfdbca0f04..f42601fe765771909519ae345ddd2b41590d284c 100644
--- a/src/proto_014_PtKathma/bin_tx_rollup_client/main_tx_rollup_client_014_PtKathma.ml
+++ b/src/proto_014_PtKathma/bin_tx_rollup_client/main_tx_rollup_client_014_PtKathma.ml
@@ -31,7 +31,80 @@ let register_signers () =
   Tezos_client_base.Client_keys.register_aggregate_signer
     (module Tezos_signer_backends.Unencrypted.Aggregate)
 
+(* FIXME: https://gitlab.com/tezos/tezos/-/issues/4025
+   Remove backwards compatible Tezos symlinks. *)
+let warn_if_argv0_name_not_octez () =
+  let executable_name =
+    (* example: tezos-tx-rollup-client-015-PtKathma *)
+    Filename.basename Sys.argv.(0)
+  in
+  let old_head = "tezos-" in
+  let new_head = "octez-" in
+  match TzString.has_prefix executable_name ~prefix:old_head with
+  | false -> ()
+  | true ->
+      let expected_name =
+        let len_prefix = String.length old_head in
+        let headless_name =
+          (* example: tx-rollup-client-015-PtKathma *)
+          String.sub
+            executable_name
+            len_prefix
+            (String.length executable_name - len_prefix)
+        in
+        let name_without_version name =
+          match headless_name |> String.starts_with ~prefix:name with
+          | false -> None
+          | true ->
+              let len_name = String.length name in
+              let version_proto =
+                (* example: -015-PtKathma *)
+                String.sub
+                  headless_name
+                  len_name
+                  (String.length headless_name - len_name)
+              in
+              let num_hyphens =
+                (* example: 2 *)
+                version_proto
+                |> String.fold_left
+                     (fun acc c -> match c with '-' -> acc + 1 | _ -> acc)
+                     0
+              in
+              let proto =
+                (* example: -PtKathma *)
+                if num_hyphens = 2 then
+                  String.sub version_proto 4 (String.length version_proto - 4)
+                else version_proto
+              in
+              Some (name ^ proto)
+        in
+        (* example: tx-rollup-client-PtKathma *)
+        let versionless_name =
+          ["accuser"; "baker"; "tx-rollup-client"; "tx-rollup-node"]
+          |> List.map name_without_version
+          |> List.find Option.is_some |> Option.join
+        in
+        (* example: octez-tx-rollup-client-PtKathma *)
+        new_head
+        ^
+        match versionless_name with
+        | None -> headless_name
+        | Some versionless_name -> versionless_name
+      in
+      Format.eprintf
+        "@[<v 2>@{<warning>@{<title>Warning@}@}@,\
+         The executable with name @{<kwd>%s@} has been renamed to @{<kwd>%s@}. \
+         The name @{<kwd>%s@} is now@,\
+         deprecated, and it will be removed in a future release. Please update@,\
+         your scripts to use the new name.@]@\n\
+         @."
+        executable_name
+        expected_name
+        executable_name
+
 let main () =
+  warn_if_argv0_name_not_octez () ;
   Configuration.parse (argv ()) >>=? fun (configuration, argv) ->
   register_signers () ;
   let cctxt = Configuration.make_unix_client_context configuration in
diff --git a/src/proto_015_PtLimaPt/bin_tx_rollup_client/main_tx_rollup_client_015_PtLimaPt.ml b/src/proto_015_PtLimaPt/bin_tx_rollup_client/main_tx_rollup_client_015_PtLimaPt.ml
index bb6b4fba9684be61a1a976ba7e37cfbfdbca0f04..f42601fe765771909519ae345ddd2b41590d284c 100644
--- a/src/proto_015_PtLimaPt/bin_tx_rollup_client/main_tx_rollup_client_015_PtLimaPt.ml
+++ b/src/proto_015_PtLimaPt/bin_tx_rollup_client/main_tx_rollup_client_015_PtLimaPt.ml
@@ -31,7 +31,80 @@ let register_signers () =
   Tezos_client_base.Client_keys.register_aggregate_signer
     (module Tezos_signer_backends.Unencrypted.Aggregate)
 
+(* FIXME: https://gitlab.com/tezos/tezos/-/issues/4025
+   Remove backwards compatible Tezos symlinks. *)
+let warn_if_argv0_name_not_octez () =
+  let executable_name =
+    (* example: tezos-tx-rollup-client-015-PtKathma *)
+    Filename.basename Sys.argv.(0)
+  in
+  let old_head = "tezos-" in
+  let new_head = "octez-" in
+  match TzString.has_prefix executable_name ~prefix:old_head with
+  | false -> ()
+  | true ->
+      let expected_name =
+        let len_prefix = String.length old_head in
+        let headless_name =
+          (* example: tx-rollup-client-015-PtKathma *)
+          String.sub
+            executable_name
+            len_prefix
+            (String.length executable_name - len_prefix)
+        in
+        let name_without_version name =
+          match headless_name |> String.starts_with ~prefix:name with
+          | false -> None
+          | true ->
+              let len_name = String.length name in
+              let version_proto =
+                (* example: -015-PtKathma *)
+                String.sub
+                  headless_name
+                  len_name
+                  (String.length headless_name - len_name)
+              in
+              let num_hyphens =
+                (* example: 2 *)
+                version_proto
+                |> String.fold_left
+                     (fun acc c -> match c with '-' -> acc + 1 | _ -> acc)
+                     0
+              in
+              let proto =
+                (* example: -PtKathma *)
+                if num_hyphens = 2 then
+                  String.sub version_proto 4 (String.length version_proto - 4)
+                else version_proto
+              in
+              Some (name ^ proto)
+        in
+        (* example: tx-rollup-client-PtKathma *)
+        let versionless_name =
+          ["accuser"; "baker"; "tx-rollup-client"; "tx-rollup-node"]
+          |> List.map name_without_version
+          |> List.find Option.is_some |> Option.join
+        in
+        (* example: octez-tx-rollup-client-PtKathma *)
+        new_head
+        ^
+        match versionless_name with
+        | None -> headless_name
+        | Some versionless_name -> versionless_name
+      in
+      Format.eprintf
+        "@[<v 2>@{<warning>@{<title>Warning@}@}@,\
+         The executable with name @{<kwd>%s@} has been renamed to @{<kwd>%s@}. \
+         The name @{<kwd>%s@} is now@,\
+         deprecated, and it will be removed in a future release. Please update@,\
+         your scripts to use the new name.@]@\n\
+         @."
+        executable_name
+        expected_name
+        executable_name
+
 let main () =
+  warn_if_argv0_name_not_octez () ;
   Configuration.parse (argv ()) >>=? fun (configuration, argv) ->
   register_signers () ;
   let cctxt = Configuration.make_unix_client_context configuration in
diff --git a/src/proto_alpha/bin_tx_rollup_client/main_tx_rollup_client_alpha.ml b/src/proto_alpha/bin_tx_rollup_client/main_tx_rollup_client_alpha.ml
index bb6b4fba9684be61a1a976ba7e37cfbfdbca0f04..f42601fe765771909519ae345ddd2b41590d284c 100644
--- a/src/proto_alpha/bin_tx_rollup_client/main_tx_rollup_client_alpha.ml
+++ b/src/proto_alpha/bin_tx_rollup_client/main_tx_rollup_client_alpha.ml
@@ -31,7 +31,80 @@ let register_signers () =
   Tezos_client_base.Client_keys.register_aggregate_signer
     (module Tezos_signer_backends.Unencrypted.Aggregate)
 
+(* FIXME: https://gitlab.com/tezos/tezos/-/issues/4025
+   Remove backwards compatible Tezos symlinks. *)
+let warn_if_argv0_name_not_octez () =
+  let executable_name =
+    (* example: tezos-tx-rollup-client-015-PtKathma *)
+    Filename.basename Sys.argv.(0)
+  in
+  let old_head = "tezos-" in
+  let new_head = "octez-" in
+  match TzString.has_prefix executable_name ~prefix:old_head with
+  | false -> ()
+  | true ->
+      let expected_name =
+        let len_prefix = String.length old_head in
+        let headless_name =
+          (* example: tx-rollup-client-015-PtKathma *)
+          String.sub
+            executable_name
+            len_prefix
+            (String.length executable_name - len_prefix)
+        in
+        let name_without_version name =
+          match headless_name |> String.starts_with ~prefix:name with
+          | false -> None
+          | true ->
+              let len_name = String.length name in
+              let version_proto =
+                (* example: -015-PtKathma *)
+                String.sub
+                  headless_name
+                  len_name
+                  (String.length headless_name - len_name)
+              in
+              let num_hyphens =
+                (* example: 2 *)
+                version_proto
+                |> String.fold_left
+                     (fun acc c -> match c with '-' -> acc + 1 | _ -> acc)
+                     0
+              in
+              let proto =
+                (* example: -PtKathma *)
+                if num_hyphens = 2 then
+                  String.sub version_proto 4 (String.length version_proto - 4)
+                else version_proto
+              in
+              Some (name ^ proto)
+        in
+        (* example: tx-rollup-client-PtKathma *)
+        let versionless_name =
+          ["accuser"; "baker"; "tx-rollup-client"; "tx-rollup-node"]
+          |> List.map name_without_version
+          |> List.find Option.is_some |> Option.join
+        in
+        (* example: octez-tx-rollup-client-PtKathma *)
+        new_head
+        ^
+        match versionless_name with
+        | None -> headless_name
+        | Some versionless_name -> versionless_name
+      in
+      Format.eprintf
+        "@[<v 2>@{<warning>@{<title>Warning@}@}@,\
+         The executable with name @{<kwd>%s@} has been renamed to @{<kwd>%s@}. \
+         The name @{<kwd>%s@} is now@,\
+         deprecated, and it will be removed in a future release. Please update@,\
+         your scripts to use the new name.@]@\n\
+         @."
+        executable_name
+        expected_name
+        executable_name
+
 let main () =
+  warn_if_argv0_name_not_octez () ;
   Configuration.parse (argv ()) >>=? fun (configuration, argv) ->
   register_signers () ;
   let cctxt = Configuration.make_unix_client_context configuration in