diff --git a/rust/Cargo.lock b/rust/Cargo.lock
--- a/rust/Cargo.lock
+++ b/rust/Cargo.lock
@@ -505,9 +505,9 @@
 
 [[package]]
 name = "libc"
-version = "0.2.81"
+version = "0.2.124"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "1482821306169ec4d07f6aca392a4681f66c75c9918aa49641a2595db64053cb"
+checksum = "21a41fed9d98f27ab1c6d161da622a4fa35e8a54a8adc24bbf3ddd0ef70b0e50"
 
 [[package]]
 name = "libm"
@@ -949,6 +949,7 @@
  "micro-timer",
  "regex",
  "users",
+ "which",
 ]
 
 [[package]]
@@ -1151,6 +1152,17 @@
 checksum = "1a143597ca7c7793eff794def352d41792a93c481eb1042423ff7ff72ba2c31f"
 
 [[package]]
+name = "which"
+version = "4.2.5"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "5c4fb54e6113b6a8772ee41c3404fb0301ac79604489467e0a9ce1f3e97c24ae"
+dependencies = [
+ "either",
+ "lazy_static",
+ "libc",
+]
+
+[[package]]
 name = "winapi"
 version = "0.3.9"
 source = "registry+https://github.com/rust-lang/crates.io-index"
diff --git a/rust/hg-core/src/exit_codes.rs b/rust/hg-core/src/exit_codes.rs
--- a/rust/hg-core/src/exit_codes.rs
+++ b/rust/hg-core/src/exit_codes.rs
@@ -17,3 +17,6 @@
 
 /// Command or feature not implemented by rhg
 pub const UNIMPLEMENTED: ExitCode = 252;
+
+/// The fallback path is not valid
+pub const INVALID_FALLBACK: ExitCode = 253;
diff --git a/rust/rhg/Cargo.toml b/rust/rhg/Cargo.toml
--- a/rust/rhg/Cargo.toml
+++ b/rust/rhg/Cargo.toml
@@ -21,3 +21,4 @@
 env_logger = "0.7.1"
 format-bytes = "0.3.0"
 users = "0.11.0"
+which = "4.2.5"
diff --git a/rust/rhg/src/error.rs b/rust/rhg/src/error.rs
--- a/rust/rhg/src/error.rs
+++ b/rust/rhg/src/error.rs
@@ -29,6 +29,9 @@
     /// `rhg` may attempt to silently fall back to Python-based `hg`, which
     /// may or may not support this feature.
     UnsupportedFeature { message: Vec<u8> },
+    /// The fallback executable does not exist (or has some other problem if
+    /// we end up being more precise about broken fallbacks).
+    InvalidFallback { path: Vec<u8>, err: String },
 }
 
 impl CommandError {
diff --git a/rust/rhg/src/main.rs b/rust/rhg/src/main.rs
--- a/rust/rhg/src/main.rs
+++ b/rust/rhg/src/main.rs
@@ -13,6 +13,7 @@
 use hg::utils::SliceExt;
 use std::collections::HashSet;
 use std::ffi::OsString;
+use std::os::unix::prelude::CommandExt;
 use std::path::PathBuf;
 use std::process::Command;
 
@@ -365,12 +366,14 @@
             }
         }
         Err(CommandError::Unsuccessful) => exit_codes::UNSUCCESSFUL,
-
         // Exit with a specific code and no error message to let a potential
         // wrapper script fallback to Python-based Mercurial.
         Err(CommandError::UnsupportedFeature { .. }) => {
             exit_codes::UNIMPLEMENTED
         }
+        Err(CommandError::InvalidFallback { .. }) => {
+            exit_codes::INVALID_FALLBACK
+        }
     }
 }
 
@@ -415,6 +418,17 @@
         } else {
             log::debug!("falling back (see trace-level log)");
             log::trace!("{}", local_to_utf8(message));
+            if let Err(err) = which::which(executable_path) {
+                exit_no_fallback(
+                    ui,
+                    OnUnsupported::Abort,
+                    Err(CommandError::InvalidFallback {
+                        path: executable.to_owned(),
+                        err: err.to_string(),
+                    }),
+                    use_detailed_exit_code,
+                )
+            }
             // `args` is now `argv[1..]` since we’ve already consumed
             // `argv[0]`
             let mut command = Command::new(executable_path);
@@ -422,19 +436,19 @@
             if let Some(initial) = initial_current_dir {
                 command.current_dir(initial);
             }
-            let result = command.status();
-            match result {
-                Ok(status) => std::process::exit(
-                    status.code().unwrap_or(exit_codes::ABORT),
-                ),
-                Err(error) => {
-                    let _ = ui.write_stderr(&format_bytes!(
-                        b"tried to fall back to a '{}' sub-process but got error {}\n",
-                        executable, format_bytes::Utf8(error)
-                    ));
-                    on_unsupported = OnUnsupported::Abort
-                }
-            }
+            // We don't use subprocess because proper signal handling is harder
+            // and we don't want to keep `rhg` around after a fallback anyway.
+            // For example, if `rhg` is run in the background and falls back to
+            // `hg` which, in turn, waits for a signal, we'll get stuck if
+            // we're doing plain subprocess.
+            //
+            // If `exec` returns, we can only assume our process is very broken
+            // (see its documentation), so only try to forward the error code
+            // when exiting.
+            let err = command.exec();
+            std::process::exit(
+                err.raw_os_error().unwrap_or(exit_codes::ABORT),
+            );
         }
     }
     exit_no_fallback(ui, on_unsupported, result, use_detailed_exit_code)
@@ -471,6 +485,13 @@
                 OnUnsupported::Fallback { .. } => unreachable!(),
             }
         }
+        Err(CommandError::InvalidFallback { path, err }) => {
+            let _ = ui.write_stderr(&format_bytes!(
+                b"abort: invalid fallback '{}': {}\n",
+                path,
+                err.as_bytes(),
+            ));
+        }
     }
     std::process::exit(exit_code(&result, use_detailed_exit_code))
 }
diff --git a/tests/test-rhg.t b/tests/test-rhg.t
--- a/tests/test-rhg.t
+++ b/tests/test-rhg.t
@@ -179,15 +179,8 @@
   [1]
 
   $ rhg cat original --exclude="*.rs" --config rhg.fallback-executable=hg-non-existent
-  tried to fall back to a 'hg-non-existent' sub-process but got error $ENOENT$
-  unsupported feature: error: Found argument '--exclude' which wasn't expected, or isn't valid in this context
-  
-  USAGE:
-      rhg cat [OPTIONS] <FILE>...
-  
-  For more information try --help
-  
-  [252]
+  abort: invalid fallback 'hg-non-existent': cannot find binary path
+  [253]
 
   $ rhg cat original --exclude="*.rs" --config rhg.fallback-executable=rhg
   Blocking recursive fallback. The 'rhg.fallback-executable = rhg' config points to `rhg` itself.