diff --git a/src/main/java/com/google/devtools/build/lib/analysis/config/ConfigurationResolver.java b/src/main/java/com/google/devtools/build/lib/analysis/config/ConfigurationResolver.java
index 56a11d2..c23d7a8 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/config/ConfigurationResolver.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/config/ConfigurationResolver.java
@@ -36,6 +36,7 @@
 import com.google.devtools.build.lib.skyframe.BuildConfigurationValue;
 import com.google.devtools.build.lib.skyframe.ConfiguredTargetFunction;
 import com.google.devtools.build.lib.skyframe.SkyframeExecutor;
+import com.google.devtools.build.lib.skyframe.TransitiveTargetKey;
 import com.google.devtools.build.lib.skyframe.TransitiveTargetValue;
 import com.google.devtools.build.lib.util.OrderedSetMultimap;
 import com.google.devtools.build.skyframe.SkyFunction;
@@ -386,7 +387,7 @@
     if (!parentConfig.trimConfigurations()) {
       return parentConfig.getAllFragments().keySet();
     }
-    SkyKey fragmentsKey = TransitiveTargetValue.key(dep);
+    SkyKey fragmentsKey = TransitiveTargetKey.of(dep);
     TransitiveTargetValue transitiveDepInfo = (TransitiveTargetValue) env.getValue(fragmentsKey);
     if (transitiveDepInfo == null) {
       // This should only be possible for tests. In actual runs, this was already called
diff --git a/src/main/java/com/google/devtools/build/lib/rules/genquery/GenQuery.java b/src/main/java/com/google/devtools/build/lib/rules/genquery/GenQuery.java
index 96e343c..308e454 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/genquery/GenQuery.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/genquery/GenQuery.java
@@ -70,6 +70,7 @@
 import com.google.devtools.build.lib.skyframe.SkyFunctions;
 import com.google.devtools.build.lib.skyframe.TargetPatternValue;
 import com.google.devtools.build.lib.skyframe.TargetPatternValue.TargetPatternKey;
+import com.google.devtools.build.lib.skyframe.TransitiveTargetKey;
 import com.google.devtools.build.lib.skyframe.TransitiveTargetValue;
 import com.google.devtools.build.lib.syntax.Type;
 import com.google.devtools.build.lib.util.Fingerprint;
@@ -214,7 +215,7 @@
     NestedSetBuilder<Label> validTargets = NestedSetBuilder.stableOrder();
     Set<PackageIdentifier> successfulPackageNames = new LinkedHashSet<>();
     for (Target target : scope) {
-      SkyKey key = TransitiveTargetValue.key(target.getLabel());
+      SkyKey key = TransitiveTargetKey.of(target.getLabel());
       TransitiveTargetValue transNode = (TransitiveTargetValue) env.getValue(key);
       if (transNode == null) {
         return null;
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 d1c0eae..b4a60ef 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
@@ -171,7 +171,7 @@
     // the first TransitiveTargetValue call happens on its dep (in trimConfigurations), so Bazel
     // associates the error with the dep, which is misleading.
     if (configuration != null && configuration.trimConfigurations()
-        && env.getValue(TransitiveTargetValue.key(lc.getLabel())) == null) {
+        && env.getValue(TransitiveTargetKey.of(lc.getLabel())) == null) {
       return null;
     }
 
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeBuildView.java b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeBuildView.java
index 7b38748..1cf6dad 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeBuildView.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeBuildView.java
@@ -400,7 +400,7 @@
       if (culprit.functionName().equals(SkyFunctions.CONFIGURED_TARGET)) {
         return ((ConfiguredTargetKey) culprit.argument()).getLabel();
       } else if (culprit.functionName().equals(SkyFunctions.TRANSITIVE_TARGET)) {
-        return (Label) culprit.argument();
+        return ((TransitiveTargetKey) culprit).getLabel();
       } else {
         return labelToLoad;
       }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java
index 7145a1d..0a51623 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java
@@ -1449,7 +1449,7 @@
         fragmentsMap.put(key.getLabel(), allFragments);
       } else {
         depsToEvaluate.add(key);
-        transitiveFragmentSkyKeys.add(TransitiveTargetValue.key(key.getLabel()));
+        transitiveFragmentSkyKeys.add(TransitiveTargetKey.of(key.getLabel()));
       }
     }
     EvaluationResult<SkyValue> fragmentsResult = evaluateSkyKeys(
@@ -1460,11 +1460,11 @@
     for (Dependency key : keys) {
       if (!depsToEvaluate.contains(key)) {
         // No fragments to compute here.
-      } else if (fragmentsResult.getError(TransitiveTargetValue.key(key.getLabel())) != null) {
+      } else if (fragmentsResult.getError(TransitiveTargetKey.of(key.getLabel())) != null) {
         labelsWithErrors.add(key.getLabel());
       } else {
         TransitiveTargetValue ttv =
-            (TransitiveTargetValue) fragmentsResult.get(TransitiveTargetValue.key(key.getLabel()));
+            (TransitiveTargetValue) fragmentsResult.get(TransitiveTargetKey.of(key.getLabel()));
         fragmentsMap.put(key.getLabel(), ttv.getTransitiveConfigFragments().toSet());
       }
     }
@@ -1683,7 +1683,7 @@
         throws InterruptedException {
       List<SkyKey> valueNames = new ArrayList<>();
       for (Label label : labelsToVisit) {
-        valueNames.add(TransitiveTargetValue.key(label));
+        valueNames.add(TransitiveTargetKey.of(label));
       }
       return buildDriver.evaluate(valueNames, keepGoing, parallelThreads, eventHandler);
     }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeLabelVisitor.java b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeLabelVisitor.java
index 742d2fa..1ffb935 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeLabelVisitor.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeLabelVisitor.java
@@ -66,7 +66,7 @@
       Entry<SkyKey, ErrorInfo> error = errors.iterator().next();
       ErrorInfo errorInfo = error.getValue();
       SkyKey topLevel = error.getKey();
-      Label topLevelLabel = (Label) topLevel.argument();
+      Label topLevelLabel = ((TransitiveTargetKey) topLevel).getLabel();
       if (!Iterables.isEmpty(errorInfo.getCycleInfo())) {
         skyframeCyclesReporter.get().reportCycles(errorInfo.getCycleInfo(), topLevel, eventHandler);
         errorAboutLoadingFailure(topLevelLabel, null, eventHandler);
@@ -84,7 +84,7 @@
       SkyKey key = errorEntry.getKey();
       ErrorInfo errorInfo = errorEntry.getValue();
       Preconditions.checkState(key.functionName().equals(SkyFunctions.TRANSITIVE_TARGET), errorEntry);
-      Label topLevelLabel = (Label) key.argument();
+      Label topLevelLabel = ((TransitiveTargetKey) key).getLabel();
       if (!Iterables.isEmpty(errorInfo.getCycleInfo())) {
         skyframeCyclesReporter.get().reportCycles(errorInfo.getCycleInfo(), key, eventHandler);
       }
@@ -97,11 +97,10 @@
       }
       warnAboutLoadingFailure(topLevelLabel, eventHandler);
     }
-    for (Label topLevelLabel : result.<Label>keyNames()) {
-      SkyKey topLevelTransitiveTargetKey = TransitiveTargetValue.key(topLevelLabel);
+    for (TransitiveTargetKey topLevelTransitiveTargetKey : result.<TransitiveTargetKey>keyNames()) {
       TransitiveTargetValue topLevelTransitiveTargetValue = result.get(topLevelTransitiveTargetKey);
       if (topLevelTransitiveTargetValue.getTransitiveRootCauses() != null) {
-        warnAboutLoadingFailure(topLevelLabel, eventHandler);
+        warnAboutLoadingFailure(topLevelTransitiveTargetKey.getLabel(), eventHandler);
       }
     }
     return false;
@@ -122,7 +121,7 @@
   private static boolean isDirectErrorFromTopLevelLabel(Label label, Set<Label> topLevelLabels,
       ErrorInfo errorInfo) {
     return errorInfo.getException() != null && topLevelLabels.contains(label)
-        && Iterables.contains(errorInfo.getRootCauses(), TransitiveTargetValue.key(label));
+        && Iterables.contains(errorInfo.getRootCauses(), TransitiveTargetKey.of(label));
   }
 
   private static void errorAboutLoadingFailure(
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/TransitiveBaseTraversalFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/TransitiveBaseTraversalFunction.java
index 726672d..1a3ac1a 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/TransitiveBaseTraversalFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/TransitiveBaseTraversalFunction.java
@@ -103,10 +103,12 @@
   abstract TargetMarkerValue getTargetMarkerValue(SkyKey targetMarkerKey, Environment env)
       throws NoSuchTargetException, NoSuchPackageException, InterruptedException;
 
+  abstract Label argumentFromKey(SkyKey key);
+
   @Override
   public SkyValue compute(SkyKey key, Environment env)
       throws TransitiveBaseTraversalFunctionException, InterruptedException {
-    Label label = (Label) key.argument();
+    Label label = argumentFromKey(key);
     LoadTargetResults loadTargetResults;
     try {
       loadTargetResults = loadTarget(env, label);
@@ -153,7 +155,7 @@
 
   @Override
   public String extractTag(SkyKey skyKey) {
-    return Label.print(((Label) skyKey.argument()));
+    return Label.print(argumentFromKey(skyKey));
   }
 
   /**
@@ -173,7 +175,7 @@
           new HashMap<>(depMap.size());
       for (Entry<SkyKey, ValueOrException2<NoSuchPackageException, NoSuchTargetException>> entry :
           depMap.entrySet()) {
-        labelDepMap.put((Label) entry.getKey().argument(), entry.getValue());
+        labelDepMap.put(argumentFromKey(entry.getKey()), entry.getValue());
       }
 
       Multimap<Attribute, Label> transitions =
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/TransitiveTargetCycleReporter.java b/src/main/java/com/google/devtools/build/lib/skyframe/TransitiveTargetCycleReporter.java
index bb2e412..a7c9b31 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/TransitiveTargetCycleReporter.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/TransitiveTargetCycleReporter.java
@@ -53,7 +53,7 @@
 
   @Override
   protected Label getLabel(SkyKey key) {
-    return (Label) key.argument();
+    return ((TransitiveTargetKey) key).getLabel();
   }
 
   @Override
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/TransitiveTargetFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/TransitiveTargetFunction.java
index 093ec2c..8614666 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/TransitiveTargetFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/TransitiveTargetFunction.java
@@ -105,8 +105,13 @@
   }
 
   @Override
+  Label argumentFromKey(SkyKey key) {
+    return ((TransitiveTargetKey) key).getLabel();
+  }
+
+  @Override
   SkyKey getKey(Label label) {
-    return TransitiveTargetValue.key(label);
+    return TransitiveTargetKey.of(label);
   }
 
   @Override
@@ -130,7 +135,7 @@
 
     for (Entry<SkyKey, ValueOrException2<NoSuchPackageException, NoSuchTargetException>> entry :
         depEntries) {
-      Label depLabel = (Label) entry.getKey().argument();
+      Label depLabel = ((TransitiveTargetKey) entry.getKey()).getLabel();
       TransitiveTargetValue transitiveTargetValue;
       try {
         transitiveTargetValue = (TransitiveTargetValue) entry.getValue().get();
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/TransitiveTargetKey.java b/src/main/java/com/google/devtools/build/lib/skyframe/TransitiveTargetKey.java
new file mode 100644
index 0000000..b4e9a61
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/TransitiveTargetKey.java
@@ -0,0 +1,70 @@
+// Copyright 2017 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.skyframe;
+
+import com.google.devtools.build.lib.cmdline.Label;
+import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
+import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
+import com.google.devtools.build.lib.util.Preconditions;
+import com.google.devtools.build.skyframe.SkyFunctionName;
+import com.google.devtools.build.skyframe.SkyKey;
+
+/**
+ * A key requesting transitive loading of all dependencies of a given label; see
+ * {@link TransitiveTargetFunction} and {@link TransitiveTargetValue}.
+ */
+@Immutable
+@ThreadSafe
+public final class TransitiveTargetKey implements SkyKey {
+  public static SkyKey of(Label label) {
+    Preconditions.checkArgument(!label.getPackageIdentifier().getRepository().isDefault());
+    return new TransitiveTargetKey(label);
+  }
+
+  private final Label label;
+
+  private TransitiveTargetKey(Label label) {
+    this.label = Preconditions.checkNotNull(label);
+  }
+
+  @Override
+  public SkyFunctionName functionName() {
+    return SkyFunctions.TRANSITIVE_TARGET;
+  }
+
+  @Override
+  public Object argument() {
+    return this;
+  }
+
+  public Label getLabel() {
+    return label;
+  }
+
+  @Override
+  public int hashCode() {
+    return 31 * functionName().hashCode() + label.hashCode();
+  }
+
+  @Override
+  public boolean equals(Object o) {
+    if (o == this) {
+      return true;
+    }
+    if (!(o instanceof TransitiveTargetKey)) {
+      return false;
+    }
+    return ((TransitiveTargetKey) o).label.equals(label);
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/TransitiveTargetValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/TransitiveTargetValue.java
index 531d215..c167d40 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/TransitiveTargetValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/TransitiveTargetValue.java
@@ -21,9 +21,6 @@
 import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
 import com.google.devtools.build.lib.packages.NoSuchTargetException;
-import com.google.devtools.build.lib.util.Preconditions;
-import com.google.devtools.build.skyframe.LegacySkyKey;
-import com.google.devtools.build.skyframe.SkyKey;
 import com.google.devtools.build.skyframe.SkyValue;
 import java.io.IOException;
 import java.io.ObjectInputStream;
@@ -129,10 +126,4 @@
   public NestedSet<Class<? extends BuildConfiguration.Fragment>> getTransitiveConfigFragments() {
     return transitiveConfigFragments;
   }
-
-  @ThreadSafe
-  public static SkyKey key(Label label) {
-    Preconditions.checkArgument(!label.getPackageIdentifier().getRepository().isDefault());
-    return LegacySkyKey.create(SkyFunctions.TRANSITIVE_TARGET, label);
-  }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/TransitiveTraversalFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/TransitiveTraversalFunction.java
index 7673069..fd99141 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/TransitiveTraversalFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/TransitiveTraversalFunction.java
@@ -44,6 +44,11 @@
     extends TransitiveBaseTraversalFunction<FirstErrorMessageAccumulator> {
 
   @Override
+  Label argumentFromKey(SkyKey key) {
+    return (Label) key.argument();
+  }
+
+  @Override
   SkyKey getKey(Label label) {
     return TransitiveTraversalValue.key(label);
   }