diff --git a/src/main/java/com/google/devtools/build/lib/bazel/repository/skylark/SkylarkRepositoryModule.java b/src/main/java/com/google/devtools/build/lib/bazel/repository/skylark/SkylarkRepositoryModule.java
index bf42816..b81a2b0 100644
--- a/src/main/java/com/google/devtools/build/lib/bazel/repository/skylark/SkylarkRepositoryModule.java
+++ b/src/main/java/com/google/devtools/build/lib/bazel/repository/skylark/SkylarkRepositoryModule.java
@@ -204,6 +204,14 @@
   @Override
   public void failWithIncompatibleUseCcConfigureFromRulesCc(
       Location location, StarlarkThread thread) throws EvalException {
-    // Noop until --incompatible_use_cc_configure_from_rules_cc is implemented.
+    if (thread.getSemantics().incompatibleUseCcConfigureFromRulesCc()) {
+      throw new EvalException(
+          location,
+          "Incompatible flag "
+              + "--incompatible_use_cc_configure_from_rules_cc has been flipped. Please use "
+              + "cc_configure and related logic from https://github.com/bazelbuild/rules_cc. "
+              + "See https://github.com/bazelbuild/bazel/issues/10134 for details and migration "
+              + "instructions.");
+    }
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/bazel/rules/BazelRulesModule.java b/src/main/java/com/google/devtools/build/lib/bazel/rules/BazelRulesModule.java
index 49b9b96..e3cd129 100644
--- a/src/main/java/com/google/devtools/build/lib/bazel/rules/BazelRulesModule.java
+++ b/src/main/java/com/google/devtools/build/lib/bazel/rules/BazelRulesModule.java
@@ -18,7 +18,6 @@
 import com.google.devtools.build.lib.analysis.BlazeDirectories;
 import com.google.devtools.build.lib.analysis.ConfiguredRuleClassProvider;
 import com.google.devtools.build.lib.analysis.config.BuildOptions;
-import com.google.devtools.build.lib.bazel.rules.cpp.BazelCppRuleClasses;
 import com.google.devtools.build.lib.bazel.rules.sh.BazelShRuleClasses;
 import com.google.devtools.build.lib.remote.options.RemoteOptions;
 import com.google.devtools.build.lib.rules.cpp.CcSkyframeFdoSupportFunction;
@@ -413,12 +412,11 @@
   public void initializeRuleClasses(ConfiguredRuleClassProvider.Builder builder) {
     builder.setToolsRepository(BazelRuleClassProvider.TOOLS_REPOSITORY);
     BazelRuleClassProvider.setup(builder);
+
     try {
       // Load auto-configuration files, it is made outside of the rule class provider so that it
       // will not be loaded for our Java tests.
       builder.addWorkspaceFileSuffix(
-          ResourceFileLoader.loadResource(BazelCppRuleClasses.class, "cc_configure.WORKSPACE"));
-      builder.addWorkspaceFileSuffix(
           ResourceFileLoader.loadResource(BazelRulesModule.class, "xcode_configure.WORKSPACE"));
       builder.addWorkspaceFileSuffix(
           ResourceFileLoader.loadResource(BazelShRuleClasses.class, "sh_configure.WORKSPACE"));
diff --git a/src/main/java/com/google/devtools/build/lib/metrics/BUILD b/src/main/java/com/google/devtools/build/lib/metrics/BUILD
index b3e9fdb..eedc59c 100644
--- a/src/main/java/com/google/devtools/build/lib/metrics/BUILD
+++ b/src/main/java/com/google/devtools/build/lib/metrics/BUILD
@@ -35,7 +35,6 @@
         "//src/main/java/com/google/devtools/build/lib:build-base",
         "//src/main/java/com/google/devtools/build/lib:runtime",
         "//src/main/java/com/google/devtools/build/lib/actions",
-        "//src/main/java/com/google/devtools/build/lib/buildeventstream",
         "//src/main/java/com/google/devtools/build/lib/buildeventstream/proto:build_event_stream_java_proto",
         "//src/main/java/com/google/devtools/common/options",
         "//third_party:guava",
diff --git a/src/main/java/com/google/devtools/build/lib/packages/StarlarkSemanticsOptions.java b/src/main/java/com/google/devtools/build/lib/packages/StarlarkSemanticsOptions.java
index e2c839e..924a4e1 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/StarlarkSemanticsOptions.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/StarlarkSemanticsOptions.java
@@ -559,6 +559,21 @@
   public boolean incompatibleDoNotSplitLinkingCmdline;
 
   @Option(
+      name = "incompatible_use_cc_configure_from_rules_cc",
+      defaultValue = "false",
+      documentationCategory = OptionDocumentationCategory.STARLARK_SEMANTICS,
+      effectTags = {OptionEffectTag.LOADING_AND_ANALYSIS},
+      metadataTags = {
+        OptionMetadataTag.INCOMPATIBLE_CHANGE,
+        OptionMetadataTag.TRIGGERED_BY_ALL_INCOMPATIBLE_CHANGES
+      },
+      help =
+          "When true, Bazel will no longer allow using cc_configure from @bazel_tools. "
+              + "Please see https://github.com/bazelbuild/bazel/issues/10134 for details and "
+              + "migration instructions.")
+  public boolean incompatibleUseCcConfigureFromRulesCc;
+
+  @Option(
       name = "incompatible_restrict_named_params",
       defaultValue = "true",
       documentationCategory = OptionDocumentationCategory.STARLARK_SEMANTICS,
@@ -652,6 +667,7 @@
                 incompatibleVisibilityPrivateAttributesAtDefinition)
             .internalSkylarkFlagTestCanary(internalSkylarkFlagTestCanary)
             .incompatibleDoNotSplitLinkingCmdline(incompatibleDoNotSplitLinkingCmdline)
+            .incompatibleUseCcConfigureFromRulesCc(incompatibleUseCcConfigureFromRulesCc)
             .incompatibleDepsetForLibrariesToLinkGetter(incompatibleDepsetForLibrariesToLinkGetter)
             .incompatibleRestrictStringEscapes(incompatibleRestrictStringEscapes)
             .incompatibleDisallowDictLookupUnhashableKeys(
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ToolchainResolutionFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/ToolchainResolutionFunction.java
index fa7c2eb..c8c308f 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/ToolchainResolutionFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ToolchainResolutionFunction.java
@@ -24,6 +24,7 @@
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.Iterables;
 import com.google.common.collect.Table;
 import com.google.devtools.build.lib.analysis.PlatformConfiguration;
 import com.google.devtools.build.lib.analysis.PlatformOptions;
@@ -521,10 +522,24 @@
   /** Exception used when a toolchain type is required but no matching toolchain is found. */
   static final class UnresolvedToolchainsException extends ToolchainException {
     UnresolvedToolchainsException(List<Label> missingToolchainTypes) {
-      super(
-          String.format(
-              "no matching toolchains found for types %s",
-              missingToolchainTypes.stream().map(Label::toString).collect(joining(", "))));
+      super(getMessage(missingToolchainTypes));
+    }
+
+    private static String getMessage(List<Label> missingToolchainTypes) {
+      if (missingToolchainTypes.size() == 1
+          && Iterables.getOnlyElement(missingToolchainTypes)
+              .toString()
+              .equals("@bazel_tools//tools/cpp:toolchain_type")) {
+        return "No matching toolchains found for types @bazel_tools//tools/cpp:toolchain_type. "
+            + "Maybe --incompatible_use_cc_configure_from_rules_cc has been flipped and there "
+            + "is no default C++ toolchain added in the WORKSPACE file? See "
+            + "https://github.com/bazelbuild/bazel/issues/10134 for details and migration "
+            + "instructions.";
+      }
+
+      return String.format(
+          "no matching toolchains found for types %s",
+          missingToolchainTypes.stream().map(Label::toString).collect(joining(", ")));
     }
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/WorkspaceASTFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/WorkspaceASTFunction.java
index a8c429d..cddb8be 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/WorkspaceASTFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/WorkspaceASTFunction.java
@@ -32,6 +32,7 @@
 import com.google.devtools.build.lib.syntax.ParserInput;
 import com.google.devtools.build.lib.syntax.Printer;
 import com.google.devtools.build.lib.syntax.StarlarkFile;
+import com.google.devtools.build.lib.syntax.StarlarkSemantics;
 import com.google.devtools.build.lib.syntax.Statement;
 import com.google.devtools.build.lib.vfs.FileSystemUtils;
 import com.google.devtools.build.lib.vfs.Path;
@@ -106,11 +107,37 @@
           throw resolvedValueError("Failed to parse WORKSPACE file");
         }
       }
+
+      StarlarkSemantics starlarkSemantics = PrecomputedValue.STARLARK_SEMANTICS.get(env);
+      if (env.valuesMissing()) {
+        return null;
+      }
+      String suffix;
+      if (resolvedFile.isPresent()) {
+        suffix = "";
+      } else if (starlarkSemantics == null) {
+        // Starlark semantics was not found, but Skyframe is happy. That means we're in the test
+        // that didn't provide complete Skyframe environment. Just move along.
+        suffix = ruleClassProvider.getDefaultWorkspaceSuffix();
+        // TODO(hlopko): Uncomment once Bazel tests pass with --all_incompatible_changes
+        // } else if (starlarkSemantics.incompatibleUseCcConfigureFromRulesCc()) {
+        //   suffix = ruleClassProvider.getDefaultWorkspaceSuffix();
+      } else if (!ruleClassProvider.getDefaultWorkspaceSuffix().contains("sh_configure")) {
+        // It might look fragile to check for sh_configure in the WORKSPACE file, but it turns
+        // out its the best approximation. The problem is that some tests want the ruleClassProvider
+        // together with logic from BazelRulesModule, some tests only want the
+        // BazelRuleClassProvider and some only a subset of that.
+        suffix = ruleClassProvider.getDefaultWorkspaceSuffix();
+      } else {
+        suffix =
+            ruleClassProvider.getDefaultWorkspaceSuffix()
+                + "\nload('@bazel_tools//tools/cpp:cc_configure.bzl', 'cc_configure')\n\n"
+                + "cc_configure()";
+      }
+
       file =
           StarlarkFile.parseWithPrelude(
-              ParserInput.create(
-                  resolvedFile.isPresent() ? "" : ruleClassProvider.getDefaultWorkspaceSuffix(),
-                  PathFragment.create("/DEFAULT.WORKSPACE.SUFFIX")),
+              ParserInput.create(suffix, PathFragment.create("/DEFAULT.WORKSPACE.SUFFIX")),
               file.getStatements());
       if (!file.ok()) {
         Event.replayEventsOn(env.getListener(), file.errors());
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/StarlarkSemantics.java b/src/main/java/com/google/devtools/build/lib/syntax/StarlarkSemantics.java
index 12a9080..d798e23 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/StarlarkSemantics.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/StarlarkSemantics.java
@@ -208,6 +208,8 @@
 
   public abstract boolean experimentalAllowTagsPropagation();
 
+  public abstract boolean incompatibleUseCcConfigureFromRulesCc();
+
   @Memoized
   @Override
   public abstract int hashCode();
@@ -281,6 +283,7 @@
           .incompatibleDepsetForLibrariesToLinkGetter(true)
           .incompatibleRestrictStringEscapes(false)
           .incompatibleDisallowDictLookupUnhashableKeys(false)
+          .incompatibleUseCcConfigureFromRulesCc(false)
           .build();
 
   /** Builder for {@link StarlarkSemantics}. All fields are mandatory. */
@@ -368,6 +371,8 @@
 
     public abstract Builder incompatibleDisallowDictLookupUnhashableKeys(boolean value);
 
+    public abstract Builder incompatibleUseCcConfigureFromRulesCc(boolean value);
+
     public abstract StarlarkSemantics build();
   }
 }
diff --git a/src/test/java/com/google/devtools/build/lib/packages/SkylarkSemanticsConsistencyTest.java b/src/test/java/com/google/devtools/build/lib/packages/SkylarkSemanticsConsistencyTest.java
index 70126bc..bfcca73 100644
--- a/src/test/java/com/google/devtools/build/lib/packages/SkylarkSemanticsConsistencyTest.java
+++ b/src/test/java/com/google/devtools/build/lib/packages/SkylarkSemanticsConsistencyTest.java
@@ -160,6 +160,7 @@
         "--incompatible_visibility_private_attributes_at_definition=" + rand.nextBoolean(),
         "--incompatible_restrict_string_escapes=" + rand.nextBoolean(),
         "--incompatible_disallow_dict_lookup_unhashable_keys=" + rand.nextBoolean(),
+        "--incompatible_use_cc_configure_from_rules_cc=" + rand.nextBoolean(),
         "--internal_skylark_flag_test_canary=" + rand.nextBoolean());
   }
 
@@ -210,6 +211,7 @@
         .incompatibleVisibilityPrivateAttributesAtDefinition(rand.nextBoolean())
         .incompatibleRestrictStringEscapes(rand.nextBoolean())
         .incompatibleDisallowDictLookupUnhashableKeys(rand.nextBoolean())
+        .incompatibleUseCcConfigureFromRulesCc(rand.nextBoolean())
         .internalSkylarkFlagTestCanary(rand.nextBoolean())
         .build();
   }
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/WorkspaceASTFunctionTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/WorkspaceASTFunctionTest.java
index b6ea916..2d3a09c 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/WorkspaceASTFunctionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/WorkspaceASTFunctionTest.java
@@ -74,6 +74,17 @@
     Mockito.when(
             env.getValue(MockitoHamcrest.argThat(new SkyKeyMatchers(SkyFunctions.PRECOMPUTED))))
         .thenReturn(new PrecomputedValue(Optional.<RootedPath>absent()));
+    Mockito.when(
+            env.getValue(
+                MockitoHamcrest.argThat(
+                    new SkyKeyMatchers(SkyFunctions.PRECOMPUTED) {
+                      @Override
+                      public boolean matches(Object item) {
+                        return super.matches(item)
+                            && item.toString().equals("PRECOMPUTED:skylark_semantics");
+                      }
+                    })))
+        .thenReturn(null);
     return env;
   }