diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/CppConfiguration.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/CppConfiguration.java
index 87f5cfb..2797940 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/CppConfiguration.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/CppConfiguration.java
@@ -396,6 +396,10 @@
     return cppOptions.legacyWholeArchive;
   }
 
+  public boolean removeLegacyWholeArchive() {
+    return cppOptions.removeLegacyWholeArchive;
+  }
+
   public boolean getInmemoryDotdFiles() {
     return cppOptions.inmemoryDotdFiles;
   }
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/CppLinkActionBuilder.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/CppLinkActionBuilder.java
index 187e1c8..1d9ec67 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/CppLinkActionBuilder.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/CppLinkActionBuilder.java
@@ -649,7 +649,7 @@
 
     boolean needWholeArchive =
         wholeArchive
-            || needWholeArchive(linkingMode, linkType, linkopts, isNativeDeps, cppConfiguration);
+            || needWholeArchive(featureConfiguration, linkType, linkopts, cppConfiguration);
     // Disallow LTO indexing for test targets that link statically, and optionally for any
     // linkstatic target (which can be used to disable LTO indexing for non-testonly cc_binary
     // built due to data dependences for a blaze test invocation). Otherwise this will provoke
@@ -1120,15 +1120,37 @@
 
   /** The default heuristic on whether we need to use whole-archive for the link. */
   private static boolean needWholeArchive(
-      Link.LinkingMode staticness,
+      FeatureConfiguration featureConfiguration,
       LinkTargetType type,
       Collection<String> linkopts,
-      boolean isNativeDeps,
       CppConfiguration cppConfig) {
-    boolean mostlyStatic = (staticness == Link.LinkingMode.STATIC);
     boolean sharedLinkopts =
         type.isDynamicLibrary() || linkopts.contains("-shared") || cppConfig.hasSharedLinkOption();
-    return (isNativeDeps || cppConfig.legacyWholeArchive()) && mostlyStatic && sharedLinkopts;
+    // Fasten your seat belt, the logic below doesn't make perfect sense and it's full of obviously
+    // missed corner cases. The world still stands and depends on this behavior, so ¯\_(ツ)_/¯.
+    if (!sharedLinkopts) {
+      // We are not producing shared library, there is no reason to use --whole-archive with
+      // executable (if the executable doesn't use the symbols, nobody else will, so --whole-archive
+      // is not needed).
+      return false;
+    }
+    if (cppConfig.removeLegacyWholeArchive()) {
+      // --incompatible_remove_legacy_whole_archive has been flipped, no --whole-archive for the
+      // entire build.
+      return false;
+    }
+    if (featureConfiguration.getRequestedFeatures().contains(CppRuleClasses.LEGACY_WHOLE_ARCHIVE)) {
+      // --incompatible_remove_legacy_whole_archive has not been flipped, and this target requested
+      // --whole-archive using features.
+      return true;
+    }
+    if (cppConfig.legacyWholeArchive()) {
+      // --incompatible_remove_legacy_whole_archive has not been flipped, so whether to
+      // use --whole-archive depends on --legacy_whole_archive.
+      return true;
+    }
+    // Hopefully future default.
+    return false;
   }
 
   private static ImmutableSet<Artifact> constructOutputs(
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/CppOptions.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/CppOptions.java
index 769c250..314919b 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/CppOptions.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/CppOptions.java
@@ -360,16 +360,18 @@
   public Label customMalloc;
 
   @Option(
-    name = "legacy_whole_archive",
-    defaultValue = "true",
-    documentationCategory = OptionDocumentationCategory.OUTPUT_PARAMETERS,
-    effectTags = {OptionEffectTag.ACTION_COMMAND_LINES, OptionEffectTag.AFFECTS_OUTPUTS},
-    help =
-        "When on, use --whole-archive for cc_binary rules that have "
-            + "linkshared=1 and either linkstatic=1 or '-static' in linkopts. "
-            + "This is for backwards compatibility only. "
-            + "A better alternative is to use alwayslink=1 where required."
-  )
+      name = "legacy_whole_archive",
+      defaultValue = "true",
+      documentationCategory = OptionDocumentationCategory.OUTPUT_PARAMETERS,
+      effectTags = {OptionEffectTag.ACTION_COMMAND_LINES, OptionEffectTag.AFFECTS_OUTPUTS},
+      metadataTags = {OptionMetadataTag.DEPRECATED},
+      help =
+          "Deprecated, superseded by --incompatible_remove_legacy_whole_archive "
+              + "(see https://github.com/bazelbuild/bazel/issues/7362 for details). "
+              + "When on, use --whole-archive for cc_binary rules that have "
+              + "linkshared=1 and either linkstatic=1 or '-static' in linkopts. "
+              + "This is for backwards compatibility only. "
+              + "A better alternative is to use alwayslink=1 where required.")
   public boolean legacyWholeArchive;
 
   @Option(
@@ -699,6 +701,20 @@
   public boolean disableLegacyCrosstoolFields;
 
   @Option(
+      name = "incompatible_remove_legacy_whole_archive",
+      defaultValue = "false",
+      documentationCategory = OptionDocumentationCategory.TOOLCHAIN,
+      effectTags = {OptionEffectTag.LOADING_AND_ANALYSIS},
+      metadataTags = {
+        OptionMetadataTag.INCOMPATIBLE_CHANGE,
+        OptionMetadataTag.TRIGGERED_BY_ALL_INCOMPATIBLE_CHANGES
+      },
+      help =
+          "If true, Bazel will not link library dependencies as whole archive by default "
+              + "(see https://github.com/bazelbuild/bazel/issues/7362 for migration instructions).")
+  public boolean removeLegacyWholeArchive;
+
+  @Option(
       name = "incompatible_remove_cpu_and_compiler_attributes_from_cc_toolchain",
       defaultValue = "false",
       documentationCategory = OptionDocumentationCategory.TOOLCHAIN,
@@ -869,6 +885,7 @@
     host.disableLegacyCrosstoolFields = disableLegacyCrosstoolFields;
     host.disableCrosstool = disableCrosstool;
     host.enableCcToolchainResolution = enableCcToolchainResolution;
+    host.removeLegacyWholeArchive = removeLegacyWholeArchive;
     return host;
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/CppRuleClasses.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/CppRuleClasses.java
index ef836e7..0399910 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/CppRuleClasses.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/CppRuleClasses.java
@@ -412,6 +412,9 @@
    */
   public static final String SUPPORTS_DYNAMIC_LINKER = "supports_dynamic_linker";
 
+  /** A feature marking that the target needs to link its deps in --whole-archive block. */
+  public static final String LEGACY_WHOLE_ARCHIVE = "legacy_whole_archive";
+
   /** Ancestor for all rules that do include scanning. */
   public static final class CcIncludeScanningRule implements RuleDefinition {
     @Override
diff --git a/src/main/java/com/google/devtools/build/lib/rules/nativedeps/NativeDepsHelper.java b/src/main/java/com/google/devtools/build/lib/rules/nativedeps/NativeDepsHelper.java
index 797f670..56cff9b 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/nativedeps/NativeDepsHelper.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/nativedeps/NativeDepsHelper.java
@@ -230,13 +230,15 @@
       sharedLibrary = nativeDeps;
     }
     FdoContext fdoContext = toolchain.getFdoContext();
+    ImmutableSet.Builder<String> requestedFeatures =
+        ImmutableSet.<String>builder().addAll(ruleContext.getFeatures()).add(STATIC_LINKING_MODE);
+    if (!ruleContext.getDisabledFeatures().contains(CppRuleClasses.LEGACY_WHOLE_ARCHIVE)) {
+      requestedFeatures.add(CppRuleClasses.LEGACY_WHOLE_ARCHIVE);
+    }
     FeatureConfiguration featureConfiguration =
         CcCommon.configureFeaturesOrReportRuleError(
             ruleContext,
-            /* requestedFeatures= */ ImmutableSet.<String>builder()
-                .addAll(ruleContext.getFeatures())
-                .add(STATIC_LINKING_MODE)
-                .build(),
+            /* requestedFeatures= */ requestedFeatures.build(),
             /* unsupportedFeatures= */ ruleContext.getDisabledFeatures(),
             toolchain);
     CppLinkActionBuilder builder =
diff --git a/src/test/java/com/google/devtools/build/lib/rules/cpp/CppLinkActionTest.java b/src/test/java/com/google/devtools/build/lib/rules/cpp/CppLinkActionTest.java
index 3392bfb..24dc831 100644
--- a/src/test/java/com/google/devtools/build/lib/rules/cpp/CppLinkActionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/rules/cpp/CppLinkActionTest.java
@@ -41,6 +41,7 @@
 import com.google.devtools.build.lib.analysis.util.ActionTester.ActionCombinationFactory;
 import com.google.devtools.build.lib.analysis.util.AnalysisMock;
 import com.google.devtools.build.lib.analysis.util.BuildViewTestCase;
+import com.google.devtools.build.lib.cmdline.LabelSyntaxException;
 import com.google.devtools.build.lib.cmdline.RepositoryName;
 import com.google.devtools.build.lib.collect.nestedset.NestedSetBuilder;
 import com.google.devtools.build.lib.collect.nestedset.Order;
@@ -212,6 +213,53 @@
   }
 
   @Test
+  public void testLegacyWholeArchive() throws Exception {
+    scratch.file(
+        "x/BUILD",
+        "cc_binary(",
+        "  name = 'libfoo.so',",
+        "  srcs = ['foo.cc'],",
+        "  linkshared = 1,",
+        ")");
+    // --incompatible_remove_legacy_whole_archive not flipped, --legacy_whole_archive wins.
+    useConfiguration(
+        "--cpu=k8", "--legacy_whole_archive", "--noincompatible_remove_legacy_whole_archive");
+    assertThat(getLibfooArguments()).contains("-Wl,-whole-archive");
+    useConfiguration(
+        "--cpu=k8", "--nolegacy_whole_archive", "--noincompatible_remove_legacy_whole_archive");
+    assertThat(getLibfooArguments()).doesNotContain("-Wl,-whole-archive");
+
+    // --incompatible_remove_legacy_whole_archive flipped, --legacy_whole_archive ignored.
+    useConfiguration(
+        "--cpu=k8", "--legacy_whole_archive", "--incompatible_remove_legacy_whole_archive");
+    assertThat(getLibfooArguments()).doesNotContain("-Wl,-whole-archive");
+    useConfiguration(
+        "--cpu=k8", "--nolegacy_whole_archive", "--incompatible_remove_legacy_whole_archive");
+    assertThat(getLibfooArguments()).doesNotContain("-Wl,-whole-archive");
+
+    // Even when --nolegacy_whole_archive, features can still add the behavior back.
+    useConfiguration(
+        "--cpu=k8",
+        "--nolegacy_whole_archive",
+        "--noincompatible_remove_legacy_whole_archive",
+        "--features=legacy_whole_archive");
+    assertThat(getLibfooArguments()).contains("-Wl,-whole-archive");
+    // Even when --nolegacy_whole_archive, features can still add the behavior, but not when
+    // --incompatible_remove_legacy_whole_archive is flipped.
+    useConfiguration(
+        "--cpu=k8",
+        "--incompatible_remove_legacy_whole_archive",
+        "--features=legacy_whole_archive");
+    assertThat(getLibfooArguments()).doesNotContain("-Wl,-whole-archive");
+  }
+
+  private List<String> getLibfooArguments() throws LabelSyntaxException {
+    ConfiguredTarget configuredTarget = getConfiguredTarget("//x:libfoo.so");
+    CppLinkAction linkAction = (CppLinkAction) getGeneratingAction(configuredTarget, "x/libfoo.so");
+    return linkAction.getArguments();
+  }
+
+  @Test
   public void testExposesRuntimeLibrarySearchDirectoriesVariable() throws Exception {
     scratch.file(
         "x/BUILD",