diff --git a/rust/private/rustc.bzl b/rust/private/rustc.bzl
index 0fe072b..97b8a17 100644
--- a/rust/private/rustc.bzl
+++ b/rust/private/rustc.bzl
@@ -425,7 +425,7 @@
 
     # Take the absolute value of hash() since it could be negative.
     path_hash = abs(hash(lib.path))
-    lib_name = get_lib_name(lib)
+    lib_name = get_lib_name(lib, for_windows = toolchain.os.startswith("windows"))
 
     prefix = "lib"
     extension = ".a"
@@ -488,7 +488,7 @@
             if _is_dylib(lib):
                 continue
             artifact = get_preferred_artifact(lib, use_pic)
-            name = get_lib_name(artifact)
+            name = get_lib_name(artifact, for_windows = toolchain.os.startswith("windows"))
 
             # On Linux-like platforms, normally library base names start with
             # `lib`, following the pattern `lib[name].(a|lo)` and we pass
@@ -1523,7 +1523,7 @@
     """
     return crate.output.dirname
 
-def _portable_link_flags(lib, use_pic, ambiguous_libs):
+def _portable_link_flags(lib, use_pic, ambiguous_libs, for_windows = False):
     artifact = get_preferred_artifact(lib, use_pic)
     if ambiguous_libs and artifact.path in ambiguous_libs:
         artifact = ambiguous_libs[artifact.path]
@@ -1544,13 +1544,31 @@
         # and adding references to these symlinks in the native section A.
         # We rely in the behavior of -Clink-arg to put the linker args
         # at the end of the linker invocation constructed by rustc.
+
+        # We skip adding `-Clink-arg=-l` for libstd and libtest from the standard library, as
+        # these two libraries are present both as an `.rlib` and a `.so` format.
+        # On linux, Rustc adds a -Bdynamic to the linker command line before the libraries specified
+        # with `-Clink-arg`, which leads to us linking against the `.so`s but not putting the
+        # corresponding value to the runtime library search paths, which results in a
+        # "cannot open shared object file: No such file or directory" error at exectuion time.
+        # We can fix this by adding a `-Clink-arg=-Bstatic` on linux, but we don't have that option for
+        # macos. The proper solution for this issue would be to remove `libtest-{hash}.so` and `libstd-{hash}.so`
+        # from the toolchain. However, it is not enough to change the toolchain's `rust_std_{...}` filegroups
+        # here: https://github.com/bazelbuild/rules_rust/blob/a9d5d894ad801002d007b858efd154e503796b9f/rust/private/repository_utils.bzl#L144
+        # because rustc manages to escape the sandbox and still finds them at linking time.
+        # We need to modify the repository rules to erase those files completely.
+        if "lib/rustlib" in artifact.path and (
+            artifact.basename.startswith("libtest-") or artifact.basename.startswith("libstd-") or
+            artifact.basename.startswith("test-") or artifact.basename.startswith("std-")
+        ):
+            return ["-lstatic=%s" % get_lib_name(artifact, for_windows)]
         return [
-            "-lstatic=%s" % get_lib_name(artifact),
-            "-Clink-arg=-l%s" % get_lib_name(artifact),
+            "-lstatic=%s" % get_lib_name(artifact, for_windows),
+            "-Clink-arg=-l%s" % (get_lib_name(artifact) if not for_windows else artifact.basename),
         ]
     elif _is_dylib(lib):
         return [
-            "-ldylib=%s" % get_lib_name(artifact),
+            "-ldylib=%s" % get_lib_name(artifact, for_windows),
         ]
 
     return []
@@ -1562,7 +1580,7 @@
         if lib.alwayslink:
             ret.extend(["-C", "link-arg=/WHOLEARCHIVE:%s" % get_preferred_artifact(lib, use_pic).path])
         else:
-            ret.extend(_portable_link_flags(lib, use_pic, ambiguous_libs))
+            ret.extend(_portable_link_flags(lib, use_pic, ambiguous_libs, for_windows = True))
     return ret
 
 def _make_link_flags_darwin(linker_input_and_use_pic_and_ambiguous_libs):
diff --git a/rust/private/utils.bzl b/rust/private/utils.bzl
index 633c90a..e342b3b 100644
--- a/rust/private/utils.bzl
+++ b/rust/private/utils.bzl
@@ -97,11 +97,12 @@
     path_parts = path.split("/")
     return [part for part in path_parts if part != "."]
 
-def get_lib_name(lib):
+def get_lib_name(lib, for_windows = False):
     """Returns the name of a library artifact, eg. libabc.a -> abc
 
     Args:
         lib (File): A library file
+        for_windows: Whether we're building on Windows.
 
     Returns:
         str: The name of the library
@@ -125,7 +126,7 @@
     # The library name is now everything minus the extension.
     libname = ".".join(comps[:-1])
 
-    if libname.startswith("lib"):
+    if libname.startswith("lib") and not for_windows:
         return libname[3:]
     else:
         return libname
diff --git a/test/native_deps/BUILD.bazel b/test/native_deps/BUILD.bazel
new file mode 100644
index 0000000..5c5d57a
--- /dev/null
+++ b/test/native_deps/BUILD.bazel
@@ -0,0 +1,26 @@
+load("@rules_cc//cc:defs.bzl", "cc_library")
+load(
+    "@rules_rust//rust:defs.bzl",
+    "rust_library",
+    "rust_test",
+)
+
+rust_library(
+    name = "transitive",
+    srcs = ["transitive.rs"],
+    edition = "2018",
+)
+
+cc_library(
+    name = "direct",
+    srcs = ["direct.cc"],
+    hdrs = ["direct.h"],
+    deps = ["transitive"],
+)
+
+rust_test(
+    name = "main",
+    srcs = ["main.rs"],
+    edition = "2018",
+    deps = ["direct"],
+)
diff --git a/test/native_deps/direct.cc b/test/native_deps/direct.cc
new file mode 100644
index 0000000..a809ae8
--- /dev/null
+++ b/test/native_deps/direct.cc
@@ -0,0 +1,6 @@
+#include "direct.h"
+
+RustStruct MakeRustStruct() {
+  RustStruct result;
+  return result;
+}
diff --git a/test/native_deps/direct.h b/test/native_deps/direct.h
new file mode 100644
index 0000000..f4f4b92
--- /dev/null
+++ b/test/native_deps/direct.h
@@ -0,0 +1,4 @@
+struct RustStruct{};
+
+extern "C" RustStruct MakeRustStruct();
+
diff --git a/test/native_deps/main.rs b/test/native_deps/main.rs
new file mode 100644
index 0000000..103d374
--- /dev/null
+++ b/test/native_deps/main.rs
@@ -0,0 +1,3 @@
+fn main() {
+    println!("Done!");
+}
diff --git a/test/native_deps/transitive.rs b/test/native_deps/transitive.rs
new file mode 100644
index 0000000..987bc30
--- /dev/null
+++ b/test/native_deps/transitive.rs
@@ -0,0 +1,2 @@
+#[repr(C)]
+pub struct RustStruct {}
diff --git a/test/native_deps/user.rs b/test/native_deps/user.rs
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/test/native_deps/user.rs
diff --git a/test/unit/native_deps/native_deps_test.bzl b/test/unit/native_deps/native_deps_test.bzl
index d066c80..43b1c07 100644
--- a/test/unit/native_deps/native_deps_test.bzl
+++ b/test/unit/native_deps/native_deps_test.bzl
@@ -30,7 +30,8 @@
     assert_argv_contains_prefix_suffix(env, action, "-Lnative=", "/native_deps")
     assert_argv_contains(env, action, "--crate-type=cdylib")
     assert_argv_contains(env, action, "-lstatic=native_dep")
-    assert_argv_contains(env, action, "-Clink-arg=-lnative_dep")
+    native_link_arg = "-Clink-arg=-lnative_dep.lib" if ctx.target_platform_has_constraint(ctx.attr._windows_constraint[platform_common.ConstraintValueInfo]) else "-Clink-arg=-lnative_dep"
+    assert_argv_contains(env, action, native_link_arg)
     assert_argv_contains_prefix(env, action, "--codegen=linker=")
     return analysistest.end(env)
 
@@ -41,22 +42,20 @@
     assert_argv_contains_prefix_suffix(env, action, "-Lnative=", "/native_deps")
     assert_argv_contains(env, action, "--crate-type=staticlib")
     assert_argv_contains(env, action, "-lstatic=native_dep")
-    assert_argv_contains(env, action, "-Clink-arg=-lnative_dep")
+    native_link_arg = "-Clink-arg=-lnative_dep.lib" if ctx.target_platform_has_constraint(ctx.attr._windows_constraint[platform_common.ConstraintValueInfo]) else "-Clink-arg=-lnative_dep"
+    assert_argv_contains(env, action, native_link_arg)
     assert_argv_contains_prefix(env, action, "--codegen=linker=")
     return analysistest.end(env)
 
 def _proc_macro_has_native_libs_test_impl(ctx):
     env = analysistest.begin(ctx)
     tut = analysistest.target_under_test(env)
-    if ctx.configuration.coverage_enabled:
-        asserts.equals(env, 2, len(tut.actions))
-    else:
-        asserts.equals(env, 1, len(tut.actions))
     action = tut.actions[0]
     assert_argv_contains_prefix_suffix(env, action, "-Lnative=", "/native_deps")
     assert_argv_contains(env, action, "--crate-type=proc-macro")
     assert_argv_contains(env, action, "-lstatic=native_dep")
-    assert_argv_contains(env, action, "-Clink-arg=-lnative_dep")
+    native_link_arg = "-Clink-arg=-lnative_dep.lib" if ctx.target_platform_has_constraint(ctx.attr._windows_constraint[platform_common.ConstraintValueInfo]) else "-Clink-arg=-lnative_dep"
+    assert_argv_contains(env, action, native_link_arg)
     assert_argv_contains_prefix(env, action, "--codegen=linker=")
     return analysistest.end(env)
 
@@ -66,7 +65,8 @@
     action = tut.actions[0]
     assert_argv_contains_prefix_suffix(env, action, "-Lnative=", "/native_deps")
     assert_argv_contains(env, action, "-lstatic=native_dep")
-    assert_argv_contains(env, action, "-Clink-arg=-lnative_dep")
+    native_link_arg = "-Clink-arg=-lnative_dep.lib" if ctx.target_platform_has_constraint(ctx.attr._windows_constraint[platform_common.ConstraintValueInfo]) else "-Clink-arg=-lnative_dep"
+    assert_argv_contains(env, action, native_link_arg)
     assert_argv_contains_prefix(env, action, "--codegen=linker=")
     return analysistest.end(env)
 
@@ -143,10 +143,18 @@
     return analysistest.end(env)
 
 rlib_has_no_native_libs_test = analysistest.make(_rlib_has_no_native_libs_test_impl)
-staticlib_has_native_libs_test = analysistest.make(_staticlib_has_native_libs_test_impl)
-cdylib_has_native_libs_test = analysistest.make(_cdylib_has_native_libs_test_impl)
-proc_macro_has_native_libs_test = analysistest.make(_proc_macro_has_native_libs_test_impl)
-bin_has_native_libs_test = analysistest.make(_bin_has_native_libs_test_impl)
+staticlib_has_native_libs_test = analysistest.make(_staticlib_has_native_libs_test_impl, attrs = {
+    "_windows_constraint": attr.label(default = Label("@platforms//os:windows")),
+})
+cdylib_has_native_libs_test = analysistest.make(_cdylib_has_native_libs_test_impl, attrs = {
+    "_windows_constraint": attr.label(default = Label("@platforms//os:windows")),
+})
+proc_macro_has_native_libs_test = analysistest.make(_proc_macro_has_native_libs_test_impl, attrs = {
+    "_windows_constraint": attr.label(default = Label("@platforms//os:windows")),
+})
+bin_has_native_libs_test = analysistest.make(_bin_has_native_libs_test_impl, attrs = {
+    "_windows_constraint": attr.label(default = Label("@platforms//os:windows")),
+})
 bin_has_native_dep_and_alwayslink_test = analysistest.make(_bin_has_native_dep_and_alwayslink_test_impl, attrs = {
     "_macos_constraint": attr.label(default = Label("@platforms//os:macos")),
     "_windows_constraint": attr.label(default = Label("@platforms//os:windows")),