diff --git a/src/main/java/com/google/devtools/build/lib/analysis/DependencyResolver.java b/src/main/java/com/google/devtools/build/lib/analysis/DependencyResolver.java
index 9d93523..54394c5 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/DependencyResolver.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/DependencyResolver.java
@@ -189,7 +189,7 @@
    *     This is needed to support {@link LateBoundDefault#useHostConfiguration()}.
    * @param aspect the aspect applied to this target (if any)
    * @param configConditions resolver for config_setting labels
-   * @param toolchainContext the toolchain context for this target
+   * @param toolchainContexts the toolchain contexts for this target
    * @param trimmingTransitionFactory the transition factory used to trim rules (note: this is a
    *     temporary feature; see the corresponding methods in ConfiguredRuleClassProvider)
    * @return a mapping of each attribute in this rule or aspects to its dependent nodes
@@ -199,7 +199,7 @@
       BuildConfiguration hostConfig,
       @Nullable Aspect aspect,
       ImmutableMap<Label, ConfigMatchingProvider> configConditions,
-      @Nullable ToolchainContext toolchainContext,
+      @Nullable ToolchainCollection<ToolchainContext> toolchainContexts,
       @Nullable TransitionFactory<Rule> trimmingTransitionFactory)
       throws EvalException, InterruptedException, InconsistentAspectOrderException {
     NestedSetBuilder<Cause> rootCauses = NestedSetBuilder.stableOrder();
@@ -209,7 +209,7 @@
             hostConfig,
             aspect != null ? ImmutableList.of(aspect) : ImmutableList.<Aspect>of(),
             configConditions,
-            toolchainContext,
+            toolchainContexts,
             rootCauses,
             trimmingTransitionFactory);
     if (!rootCauses.isEmpty()) {
@@ -243,7 +243,7 @@
    *     This is needed to support {@link LateBoundDefault#useHostConfiguration()}.
    * @param aspects the aspects applied to this target (if any)
    * @param configConditions resolver for config_setting labels
-   * @param toolchainContext the toolchain context for this target
+   * @param toolchainContexts the toolchain contexts for this target
    * @param trimmingTransitionFactory the transition factory used to trim rules (note: this is a
    *     temporary feature; see the corresponding methods in ConfiguredRuleClassProvider)
    * @param rootCauses collector for dep labels that can't be (loading phase) loaded
@@ -254,7 +254,7 @@
       BuildConfiguration hostConfig,
       Iterable<Aspect> aspects,
       ImmutableMap<Label, ConfigMatchingProvider> configConditions,
-      @Nullable ToolchainContext toolchainContext,
+      @Nullable ToolchainCollection<ToolchainContext> toolchainContexts,
       NestedSetBuilder<Cause> rootCauses,
       @Nullable TransitionFactory<Rule> trimmingTransitionFactory)
       throws EvalException, InterruptedException, InconsistentAspectOrderException {
@@ -279,7 +279,7 @@
     } else if (target instanceof Rule) {
       fromRule = (Rule) target;
       attributeMap = ConfiguredAttributeMapper.of(fromRule, configConditions);
-      visitRule(node, hostConfig, aspects, attributeMap, toolchainContext, outgoingLabels);
+      visitRule(node, hostConfig, aspects, attributeMap, toolchainContexts, outgoingLabels);
     } else if (target instanceof PackageGroup) {
       outgoingLabels.putAll(VISIBILITY_DEPENDENCY, ((PackageGroup) target).getIncludes());
     } else {
@@ -294,7 +294,7 @@
 
     OrderedSetMultimap<DependencyKind, PartiallyResolvedDependency> partiallyResolvedDeps =
         partiallyResolveDependencies(
-            outgoingLabels, fromRule, attributeMap, toolchainContext, aspects);
+            outgoingLabels, fromRule, attributeMap, toolchainContexts, aspects);
 
     OrderedSetMultimap<DependencyKind, Dependency> outgoingEdges =
         fullyResolveDependencies(
@@ -316,7 +316,7 @@
           OrderedSetMultimap<DependencyKind, Label> outgoingLabels,
           @Nullable Rule fromRule,
           ConfiguredAttributeMapper attributeMap,
-          @Nullable ToolchainContext toolchainContext,
+          @Nullable ToolchainCollection<ToolchainContext> toolchainContexts,
           Iterable<Aspect> aspects) {
     OrderedSetMultimap<DependencyKind, PartiallyResolvedDependency> partiallyResolvedDeps =
         OrderedSetMultimap.create();
@@ -361,8 +361,12 @@
           aspects, attribute.getName(), entry.getKey().getOwningAspect(), propagatingAspects);
 
       Label executionPlatformLabel = null;
-      if (toolchainContext != null && toolchainContext.executionPlatform() != null) {
-        executionPlatformLabel = toolchainContext.executionPlatform().label();
+      // TODO(b/151742236): support transitions to other ({@link ExecGroup defined}) execution
+      // platforms
+      if (toolchainContexts != null
+          && toolchainContexts.getDefaultToolchainContext().executionPlatform() != null) {
+        executionPlatformLabel =
+            toolchainContexts.getDefaultToolchainContext().executionPlatform().label();
       }
       AttributeTransitionData attributeTransitionData =
           AttributeTransitionData.builder()
@@ -426,7 +430,7 @@
       BuildConfiguration hostConfig,
       Iterable<Aspect> aspects,
       ConfiguredAttributeMapper attributeMap,
-      @Nullable ToolchainContext toolchainContext,
+      @Nullable ToolchainCollection<ToolchainContext> toolchainContexts,
       OrderedSetMultimap<DependencyKind, Label> outgoingLabels)
       throws EvalException {
     Preconditions.checkArgument(node.getTarget() instanceof Rule, node);
@@ -479,8 +483,8 @@
           rule.getPackage().getDefaultRestrictedTo());
     }
 
-    if (toolchainContext != null) {
-      outgoingLabels.putAll(TOOLCHAIN_DEPENDENCY, toolchainContext.resolvedToolchainLabels());
+    if (toolchainContexts != null) {
+      outgoingLabels.putAll(TOOLCHAIN_DEPENDENCY, toolchainContexts.getRequiredToolchains());
     }
 
     if (!rule.isAttributeValueExplicitlySpecified(RuleClass.APPLICABLE_LICENSES_ATTR)) {
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/ToolchainCollection.java b/src/main/java/com/google/devtools/build/lib/analysis/ToolchainCollection.java
new file mode 100644
index 0000000..1f62133
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/analysis/ToolchainCollection.java
@@ -0,0 +1,88 @@
+// Copyright 2020 The Bazel Authors. All rights reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//    http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+package com.google.devtools.build.lib.analysis;
+
+import com.google.common.base.Preconditions;
+import com.google.common.collect.ImmutableMap;
+import com.google.common.collect.ImmutableSet;
+import com.google.devtools.build.lib.cmdline.Label;
+import java.util.Collection;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.Map;
+import java.util.Set;
+
+/**
+ * A wrapper class for a map of exec_group names to their relevent ToolchainContext.
+ *
+ * @param <T> any class that extends ToolchainCollection so this can be used, e.g., both before and
+ *     after toolchain resolution.
+ */
+public class ToolchainCollection<T extends ToolchainContext> {
+  private static final String DEFAULT_EXEC_GROUP_NAME = "default_exec_group";
+
+  /** A map of execution group names to toolchain contexts. */
+  private final ImmutableMap<String, T> toolchainContexts;
+
+  private ToolchainCollection(Map<String, T> contexts) {
+    Preconditions.checkArgument(contexts.containsKey(DEFAULT_EXEC_GROUP_NAME));
+    toolchainContexts = ImmutableMap.copyOf(contexts);
+  }
+
+  /** Builder for ToolchainCollection. */
+  public static class Builder<T extends ToolchainContext> {
+    private final Map<String, T> toolchainContexts = new HashMap<>();
+
+    public ToolchainCollection<T> build() {
+      return new ToolchainCollection<>(toolchainContexts);
+    }
+
+    public void addContext(String execGroup, T context) {
+      Preconditions.checkArgument(
+          !toolchainContexts.containsKey(execGroup),
+          "Duplicate add of '%s' exec group to toolchain collection.",
+          execGroup);
+      toolchainContexts.put(execGroup, context);
+    }
+
+    public Builder<T> addDefaultContext(T context) {
+      addContext(DEFAULT_EXEC_GROUP_NAME, context);
+      return this;
+    }
+  }
+
+  public T getDefaultToolchainContext() {
+    return toolchainContexts.get(DEFAULT_EXEC_GROUP_NAME);
+  }
+
+  public T getToolchainContext(String execGroup) {
+    return toolchainContexts.get(execGroup);
+  }
+
+  public ImmutableSet<Label> getRequiredToolchains() {
+    Set<Label> requiredToolchains = new HashSet<>();
+    for (T context : toolchainContexts.values()) {
+      requiredToolchains.addAll(context.resolvedToolchainLabels());
+    }
+    return ImmutableSet.copyOf(requiredToolchains);
+  }
+
+  public ToolchainCollection<ToolchainContext> asToolchainContexts() {
+    return new ToolchainCollection<>(ImmutableMap.copyOf(toolchainContexts));
+  }
+
+  public Collection<T> getContexts() {
+    return toolchainContexts.values();
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/query2/cquery/ConfiguredTargetAccessor.java b/src/main/java/com/google/devtools/build/lib/query2/cquery/ConfiguredTargetAccessor.java
index b6973fb..2b8b2ed 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/cquery/ConfiguredTargetAccessor.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/cquery/ConfiguredTargetAccessor.java
@@ -23,6 +23,7 @@
 import com.google.common.collect.Multimaps;
 import com.google.devtools.build.lib.analysis.ConfiguredTarget;
 import com.google.devtools.build.lib.analysis.PlatformConfiguration;
+import com.google.devtools.build.lib.analysis.ToolchainCollection;
 import com.google.devtools.build.lib.analysis.ToolchainContext;
 import com.google.devtools.build.lib.analysis.config.BuildConfiguration;
 import com.google.devtools.build.lib.analysis.config.ConfigMatchingProvider;
@@ -30,6 +31,7 @@
 import com.google.devtools.build.lib.analysis.configuredtargets.RuleConfiguredTarget;
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.packages.ConfiguredAttributeMapper;
+import com.google.devtools.build.lib.packages.ExecGroup;
 import com.google.devtools.build.lib.packages.NoSuchTargetException;
 import com.google.devtools.build.lib.packages.Rule;
 import com.google.devtools.build.lib.packages.Target;
@@ -45,6 +47,7 @@
 import com.google.devtools.build.lib.skyframe.UnloadedToolchainContext;
 import com.google.devtools.build.skyframe.WalkableGraph;
 import java.util.List;
+import java.util.Map;
 import java.util.Set;
 import javax.annotation.Nullable;
 
@@ -196,12 +199,13 @@
   }
 
   @Nullable
-  public ToolchainContext getToolchainContext(Target target, BuildConfiguration config) {
-    return getToolchainContext(target, config, walkableGraph);
+  ToolchainCollection<ToolchainContext> getToolchainContexts(
+      Target target, BuildConfiguration config) {
+    return getToolchainContexts(target, config, walkableGraph);
   }
 
   @Nullable
-  public static ToolchainContext getToolchainContext(
+  private static ToolchainCollection<ToolchainContext> getToolchainContexts(
       Target target, BuildConfiguration config, WalkableGraph walkableGraph) {
     if (!(target instanceof Rule)) {
       return null;
@@ -213,18 +217,42 @@
     }
 
     ImmutableSet<Label> requiredToolchains = rule.getRuleClassObject().getRequiredToolchains();
-
     // Collect local (target, rule) constraints for filtering out execution platforms.
     ImmutableSet<Label> execConstraintLabels =
         getExecutionPlatformConstraints(rule, config.getFragment(PlatformConfiguration.class));
+    ImmutableMap<String, ExecGroup> execGroups = rule.getRuleClassObject().getExecGroups();
+
+    ToolchainCollection.Builder<UnloadedToolchainContext> toolchainContexts =
+        new ToolchainCollection.Builder<>();
     try {
-      return (UnloadedToolchainContext)
-          walkableGraph.getValue(
-              UnloadedToolchainContext.key()
-                  .configurationKey(BuildConfigurationValue.key(config))
-                  .requiredToolchainTypeLabels(requiredToolchains)
-                  .execConstraintLabels(execConstraintLabels)
-                  .build());
+      for (Map.Entry<String, ExecGroup> group : execGroups.entrySet()) {
+        ExecGroup execGroup = group.getValue();
+        UnloadedToolchainContext context =
+            (UnloadedToolchainContext)
+                walkableGraph.getValue(
+                    UnloadedToolchainContext.key()
+                        .configurationKey(BuildConfigurationValue.key(config))
+                        .requiredToolchainTypeLabels(execGroup.getRequiredToolchains())
+                        .execConstraintLabels(execGroup.getExecutionPlatformConstraints())
+                        .build());
+        if (context == null) {
+          return null;
+        }
+        toolchainContexts.addContext(group.getKey(), context);
+      }
+      UnloadedToolchainContext defaultContext =
+          (UnloadedToolchainContext)
+              walkableGraph.getValue(
+                  UnloadedToolchainContext.key()
+                      .configurationKey(BuildConfigurationValue.key(config))
+                      .requiredToolchainTypeLabels(requiredToolchains)
+                      .execConstraintLabels(execConstraintLabels)
+                      .build());
+      if (defaultContext == null) {
+        return null;
+      }
+      toolchainContexts.addDefaultContext(defaultContext);
+      return toolchainContexts.build().asToolchainContexts();
     } catch (InterruptedException e) {
       throw new IllegalStateException(
           "Thread interrupted in the middle of getting a ToolchainContext.", e);
diff --git a/src/main/java/com/google/devtools/build/lib/query2/cquery/TransitionsOutputFormatterCallback.java b/src/main/java/com/google/devtools/build/lib/query2/cquery/TransitionsOutputFormatterCallback.java
index 12e244c..58f280c 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/cquery/TransitionsOutputFormatterCallback.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/cquery/TransitionsOutputFormatterCallback.java
@@ -22,6 +22,7 @@
 import com.google.devtools.build.lib.analysis.DependencyResolver.DependencyKind;
 import com.google.devtools.build.lib.analysis.DependencyResolver.InconsistentAspectOrderException;
 import com.google.devtools.build.lib.analysis.TargetAndConfiguration;
+import com.google.devtools.build.lib.analysis.ToolchainCollection;
 import com.google.devtools.build.lib.analysis.ToolchainContext;
 import com.google.devtools.build.lib.analysis.config.BuildConfiguration;
 import com.google.devtools.build.lib.analysis.config.BuildOptions;
@@ -118,7 +119,8 @@
           ((RuleConfiguredTarget) configuredTarget).getConfigConditions();
 
       // Get a ToolchainContext to use for dependency resolution.
-      ToolchainContext toolchainContext = accessor.getToolchainContext(target, config);
+      ToolchainCollection<ToolchainContext> toolchainContexts =
+          accessor.getToolchainContexts(target, config);
       try {
         // We don't actually use fromOptions in our implementation of
         // DependencyResolver but passing to avoid passing a null and since we have the information
@@ -130,7 +132,7 @@
                     hostConfiguration,
                     /*aspect=*/ null,
                     configConditions,
-                    toolchainContext,
+                    toolchainContexts,
                     trimmingTransitionFactory);
       } catch (EvalException | InconsistentAspectOrderException e) {
         throw new InterruptedException(e.getMessage());
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/AspectFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/AspectFunction.java
index 1ddd460..728c2b4 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/AspectFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/AspectFunction.java
@@ -32,6 +32,7 @@
 import com.google.devtools.build.lib.analysis.DuplicateException;
 import com.google.devtools.build.lib.analysis.ResolvedToolchainContext;
 import com.google.devtools.build.lib.analysis.TargetAndConfiguration;
+import com.google.devtools.build.lib.analysis.ToolchainCollection;
 import com.google.devtools.build.lib.analysis.config.BuildConfiguration;
 import com.google.devtools.build.lib.analysis.config.BuildOptions;
 import com.google.devtools.build.lib.analysis.config.ConfigMatchingProvider;
@@ -420,7 +421,11 @@
                 originalTargetAndAspectConfiguration,
                 aspectPath,
                 configConditions,
-                unloadedToolchainContext,
+                unloadedToolchainContext == null
+                    ? null
+                    : new ToolchainCollection.Builder<>()
+                        .addDefaultContext(unloadedToolchainContext)
+                        .build(),
                 ruleClassProvider,
                 view.getHostConfiguration(originalTargetAndAspectConfiguration.getConfiguration()),
                 transitivePackagesForPackageRootResolution,
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ConfiguredTargetFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/ConfiguredTargetFunction.java
index 9f8fe0c..72a1821 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/ConfiguredTargetFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ConfiguredTargetFunction.java
@@ -39,6 +39,8 @@
 import com.google.devtools.build.lib.analysis.PlatformConfiguration;
 import com.google.devtools.build.lib.analysis.ResolvedToolchainContext;
 import com.google.devtools.build.lib.analysis.TargetAndConfiguration;
+import com.google.devtools.build.lib.analysis.ToolchainCollection;
+import com.google.devtools.build.lib.analysis.ToolchainContext;
 import com.google.devtools.build.lib.analysis.config.BuildConfiguration;
 import com.google.devtools.build.lib.analysis.config.BuildOptions;
 import com.google.devtools.build.lib.analysis.config.ConfigMatchingProvider;
@@ -59,6 +61,7 @@
 import com.google.devtools.build.lib.events.StoredEventHandler;
 import com.google.devtools.build.lib.packages.Aspect;
 import com.google.devtools.build.lib.packages.BuildType;
+import com.google.devtools.build.lib.packages.ExecGroup;
 import com.google.devtools.build.lib.packages.NoSuchTargetException;
 import com.google.devtools.build.lib.packages.NonconfigurableAttributeMapper;
 import com.google.devtools.build.lib.packages.Package;
@@ -70,6 +73,7 @@
 import com.google.devtools.build.lib.packages.TargetUtils;
 import com.google.devtools.build.lib.skyframe.AspectFunction.AspectCreationException;
 import com.google.devtools.build.lib.skyframe.SkyframeExecutor.BuildViewProvider;
+import com.google.devtools.build.lib.skyframe.UnloadedToolchainContext.UnloadedToolchainContextKey;
 import com.google.devtools.build.lib.syntax.EvalException;
 import com.google.devtools.build.lib.util.OrderedSetMultimap;
 import com.google.devtools.build.skyframe.SkyFunction;
@@ -79,6 +83,7 @@
 import com.google.devtools.build.skyframe.ValueOrException;
 import java.util.ArrayList;
 import java.util.Collection;
+import java.util.HashMap;
 import java.util.HashSet;
 import java.util.LinkedHashMap;
 import java.util.List;
@@ -250,7 +255,7 @@
 
     SkyframeDependencyResolver resolver = view.createDependencyResolver(env);
 
-    UnloadedToolchainContext unloadedToolchainContext = null;
+    ToolchainCollection<UnloadedToolchainContext> unloadedToolchainContexts = null;
 
     // TODO(janakr): this call may tie up this thread indefinitely, reducing the parallelism of
     //  Skyframe. This is a strict improvement over the prior state of the code, in which we ran
@@ -284,7 +289,7 @@
       }
 
       // Determine what toolchains are needed by this target.
-      unloadedToolchainContext = computeUnloadedToolchainContext(env, ctgValue);
+      unloadedToolchainContexts = computeUnloadedToolchainContexts(env, ctgValue);
       if (env.valuesMissing()) {
         return null;
       }
@@ -297,7 +302,9 @@
               ctgValue,
               ImmutableList.<Aspect>of(),
               configConditions,
-              unloadedToolchainContext,
+              unloadedToolchainContexts == null
+                  ? null
+                  : unloadedToolchainContexts.asToolchainContexts(),
               ruleClassProvider,
               view.getHostConfiguration(configuration),
               transitivePackagesForPackageRootResolution,
@@ -314,13 +321,14 @@
       Preconditions.checkNotNull(depValueMap);
 
       // Load the requested toolchains into the ToolchainContext, now that we have dependencies.
+      // TODO(b/151742236); load non-default {@link ExecGroup} toolchains.
       ResolvedToolchainContext toolchainContext = null;
-      if (unloadedToolchainContext != null) {
+      if (unloadedToolchainContexts != null) {
         String targetDescription = target.toString();
         toolchainContext =
             ResolvedToolchainContext.load(
                 target.getPackage().getRepositoryMapping(),
-                unloadedToolchainContext,
+                unloadedToolchainContexts.getDefaultToolchainContext(),
                 targetDescription,
                 depValueMap.get(DependencyResolver.TOOLCHAIN_DEPENDENCY));
       }
@@ -345,8 +353,10 @@
         ConfiguredValueCreationException cvce = (ConfiguredValueCreationException) e.getCause();
 
         // Check if this is caused by an unresolved toolchain, and report it as such.
-        if (unloadedToolchainContext != null) {
-          UnloadedToolchainContext finalUnloadedToolchainContext = unloadedToolchainContext;
+        // TODO(b/151742236): check non-default {@link ExecGroup} toolchains as well.
+        if (unloadedToolchainContexts != null) {
+          UnloadedToolchainContext finalUnloadedToolchainContext =
+              unloadedToolchainContexts.getDefaultToolchainContext();
           Set<Label> toolchainDependencyErrors =
               cvce.getRootCauses().toList().stream()
                   .map(Cause::getLabel)
@@ -419,7 +429,7 @@
    * to check the result is valid.
    */
   @Nullable
-  private UnloadedToolchainContext computeUnloadedToolchainContext(
+  private ToolchainCollection<UnloadedToolchainContext> computeUnloadedToolchainContexts(
       Environment env, TargetAndConfiguration targetAndConfig)
       throws InterruptedException, ToolchainException {
     if (!(targetAndConfig.getTarget() instanceof Rule)) {
@@ -431,7 +441,14 @@
     }
     BuildConfiguration configuration = targetAndConfig.getConfiguration();
 
-    ImmutableSet<Label> requiredToolchains = rule.getRuleClassObject().getRequiredToolchains();
+    ImmutableSet<Label> requiredDefaultToolchains =
+        rule.getRuleClassObject().getRequiredToolchains();
+    // Collect local (target, rule) constraints for filtering out execution platforms.
+    ImmutableSet<Label> defaultExecConstraintLabels =
+        getExecutionPlatformConstraints(
+            rule, configuration.getFragment(PlatformConfiguration.class));
+
+    ImmutableMap<String, ExecGroup> execGroups = rule.getRuleClassObject().getExecGroups();
 
     // The toolchain context's options are the parent rule's options with manual trimming
     // auto-applied. This means toolchains don't inherit feature flags. This helps build
@@ -464,19 +481,50 @@
             configuration.getFragmentsMap().keySet(),
             BuildOptions.diffForReconstruction(defaultBuildOptions, toolchainOptions));
 
-    // Collect local (target, rule) constraints for filtering out execution platforms.
-    ImmutableSet<Label> execConstraintLabels =
-        getExecutionPlatformConstraints(
-            rule, configuration.getFragment(PlatformConfiguration.class));
-    return (UnloadedToolchainContext)
-        env.getValueOrThrow(
-            UnloadedToolchainContext.key()
-                .configurationKey(toolchainConfig)
-                .requiredToolchainTypeLabels(requiredToolchains)
-                .execConstraintLabels(execConstraintLabels)
-                .shouldSanityCheckConfiguration(configuration.trimConfigurationsRetroactively())
-                .build(),
-            ToolchainException.class);
+    Map<String, UnloadedToolchainContextKey> unloadedToolchainContextKeys = new HashMap<>();
+    String targetUnloadedToolchainContext = "target-unloaded-toolchain-context";
+    unloadedToolchainContextKeys.put(
+        targetUnloadedToolchainContext,
+        UnloadedToolchainContext.key()
+            .configurationKey(toolchainConfig)
+            .requiredToolchainTypeLabels(requiredDefaultToolchains)
+            .execConstraintLabels(defaultExecConstraintLabels)
+            .shouldSanityCheckConfiguration(configuration.trimConfigurationsRetroactively())
+            .build());
+    for (Map.Entry<String, ExecGroup> group : execGroups.entrySet()) {
+      ExecGroup execGroup = group.getValue();
+      unloadedToolchainContextKeys.put(
+          group.getKey(),
+          UnloadedToolchainContext.key()
+              .configurationKey(toolchainConfig)
+              .requiredToolchainTypeLabels(execGroup.getRequiredToolchains())
+              .execConstraintLabels(execGroup.getExecutionPlatformConstraints())
+              .shouldSanityCheckConfiguration(configuration.trimConfigurationsRetroactively())
+              .build());
+    }
+
+    Map<SkyKey, ValueOrException<ToolchainException>> values =
+        env.getValuesOrThrow(unloadedToolchainContextKeys.values(), ToolchainException.class);
+
+    boolean valuesMissing = env.valuesMissing();
+
+    ToolchainCollection.Builder<UnloadedToolchainContext> toolchainContexts =
+        valuesMissing ? null : new ToolchainCollection.Builder<>();
+    for (Map.Entry<String, UnloadedToolchainContextKey> unloadedToolchainContextKey :
+        unloadedToolchainContextKeys.entrySet()) {
+      UnloadedToolchainContext unloadedToolchainContext =
+          (UnloadedToolchainContext) values.get(unloadedToolchainContextKey.getValue()).get();
+      if (!valuesMissing) {
+        String execGroup = unloadedToolchainContextKey.getKey();
+        if (execGroup.equals(targetUnloadedToolchainContext)) {
+          toolchainContexts.addDefaultContext(unloadedToolchainContext);
+        } else {
+          toolchainContexts.addContext(execGroup, unloadedToolchainContext);
+        }
+      }
+    }
+
+    return valuesMissing ? null : toolchainContexts.build();
   }
 
   /**
@@ -513,7 +561,7 @@
    * @param ctgValue the label and the configuration of the node
    * @param aspects
    * @param configConditions the configuration conditions for evaluating the attributes of the node
-   * @param toolchainContext the toolchain context for this target
+   * @param toolchainContexts the toolchain context for this target
    * @param ruleClassProvider rule class provider for determining the right configuration fragments
    *     to apply to deps
    * @param hostConfiguration the host configuration. There's a noticeable performance hit from
@@ -530,7 +578,7 @@
       TargetAndConfiguration ctgValue,
       Iterable<Aspect> aspects,
       ImmutableMap<Label, ConfigMatchingProvider> configConditions,
-      @Nullable UnloadedToolchainContext toolchainContext,
+      @Nullable ToolchainCollection<ToolchainContext> toolchainContexts,
       RuleClassProvider ruleClassProvider,
       BuildConfiguration hostConfiguration,
       @Nullable NestedSetBuilder<Package> transitivePackagesForPackageRootResolution,
@@ -547,7 +595,7 @@
               hostConfiguration,
               aspects,
               configConditions,
-              toolchainContext,
+              toolchainContexts,
               transitiveRootCauses,
               ((ConfiguredRuleClassProvider) ruleClassProvider).getTrimmingTransitionFactory());
     } catch (EvalException e) {
diff --git a/src/test/java/com/google/devtools/build/lib/analysis/util/BuildViewForTesting.java b/src/test/java/com/google/devtools/build/lib/analysis/util/BuildViewForTesting.java
index 7bb75a7..9f6d341 100644
--- a/src/test/java/com/google/devtools/build/lib/analysis/util/BuildViewForTesting.java
+++ b/src/test/java/com/google/devtools/build/lib/analysis/util/BuildViewForTesting.java
@@ -41,6 +41,7 @@
 import com.google.devtools.build.lib.analysis.ResolvedToolchainContext;
 import com.google.devtools.build.lib.analysis.RuleContext;
 import com.google.devtools.build.lib.analysis.TargetAndConfiguration;
+import com.google.devtools.build.lib.analysis.ToolchainCollection;
 import com.google.devtools.build.lib.analysis.ToolchainContext;
 import com.google.devtools.build.lib.analysis.TopLevelArtifactContext;
 import com.google.devtools.build.lib.analysis.ViewCreationFailedException;
@@ -275,7 +276,7 @@
       final ExtendedEventHandler eventHandler,
       final ConfiguredTarget ct,
       BuildConfigurationCollection configurations,
-      @Nullable ToolchainContext toolchainContext)
+      @Nullable ToolchainCollection<ToolchainContext> toolchainContexts)
       throws EvalException, InterruptedException, InconsistentAspectOrderException,
           StarlarkTransition.TransitionException, InvalidConfigurationException {
 
@@ -332,7 +333,7 @@
         configurations.getHostConfiguration(),
         /*aspect=*/ null,
         getConfigurableAttributeKeysForTesting(eventHandler, ctgNode),
-        toolchainContext,
+        toolchainContexts,
         ruleClassProvider.getTrimmingTransitionFactory());
   }
 
@@ -367,12 +368,12 @@
       final ExtendedEventHandler eventHandler,
       ConfiguredTarget target,
       BuildConfigurationCollection configurations,
-      @Nullable ToolchainContext toolchainContext)
+      @Nullable ToolchainCollection<ToolchainContext> toolchainContexts)
       throws EvalException, InvalidConfigurationException, InterruptedException,
           InconsistentAspectOrderException, StarlarkTransition.TransitionException {
     OrderedSetMultimap<DependencyKind, Dependency> depNodeNames =
         getDirectPrerequisiteDependenciesForTesting(
-            eventHandler, target, configurations, toolchainContext);
+            eventHandler, target, configurations, toolchainContexts);
 
     ImmutableMultimap<Dependency, ConfiguredTargetAndData> cts =
         skyframeExecutor.getConfiguredTargetMapForTesting(
@@ -509,7 +510,13 @@
 
     OrderedSetMultimap<DependencyKind, ConfiguredTargetAndData> prerequisiteMap =
         getPrerequisiteMapForTesting(
-            eventHandler, configuredTarget, configurations, unloadedToolchainContext);
+            eventHandler,
+            configuredTarget,
+            configurations,
+            // TODO(b/151742236): make tests aware of exec groups
+            new ToolchainCollection.Builder<>()
+                .addDefaultContext(unloadedToolchainContext)
+                .build());
     String targetDescription = target.toString();
     ResolvedToolchainContext toolchainContext =
         ResolvedToolchainContext.load(
diff --git a/src/test/shell/bazel/toolchain_test.sh b/src/test/shell/bazel/toolchain_test.sh
index 4df2123..f28caa4 100755
--- a/src/test/shell/bazel/toolchain_test.sh
+++ b/src/test/shell/bazel/toolchain_test.sh
@@ -1742,6 +1742,37 @@
   expect_log "//demo:tool target platform: //platforms:platform2"
 }
 
+function test_deps_includes_exec_group_toolchain() {
+  write_register_toolchain
+  write_test_toolchain
+
+  cat >>toolchain/rule_use_toolchain.bzl <<EOF
+def _impl(ctx):
+  # TODO(b/151742236): test accessing exec_group here
+  return []
+
+use_toolchain = rule(
+  implementation = _impl,
+  exec_groups = {
+    "group": exec_group(
+      toolchains = ["//toolchain:test_toolchain"],
+    ),
+  },
+)
+EOF
+
+  mkdir -p demo
+  cat >> demo/BUILD <<EOF
+load("//toolchain:rule_use_toolchain.bzl", "use_toolchain")
+
+use_toolchain(name = "use")
+EOF
+
+  bazel cquery "deps(//demo:use, 1)" --experimental_exec_groups \
+    &> $TEST_log || fail "Build failed"
+  expect_log "//toolchain:test_toolchain"
+}
+
 # TODO(katre): Test using toolchain-provided make variables from a genrule.
 
 run_suite "toolchain tests"