diff --git a/src/main/java/com/google/devtools/build/lib/collect/nestedset/Depset.java b/src/main/java/com/google/devtools/build/lib/collect/nestedset/Depset.java
index b013822..332092a 100644
--- a/src/main/java/com/google/devtools/build/lib/collect/nestedset/Depset.java
+++ b/src/main/java/com/google/devtools/build/lib/collect/nestedset/Depset.java
@@ -95,7 +95,7 @@
   private final ElementType elemType;
   private final NestedSet<?> set;
 
-  private Depset(ElementType elemType, NestedSet<?> set) {
+  Depset(ElementType elemType, NestedSet<?> set) {
     this.elemType = Preconditions.checkNotNull(elemType, "element type cannot be null");
     this.set = set;
   }
@@ -189,6 +189,9 @@
   // two arguments: of(Class<T> elemType, NestedSet<T> set). We could also avoid the allocations
   // done by ElementType.of().
   public static <T> Depset of(ElementType elemType, NestedSet<T> set) {
+    if (set.isEmpty()) {
+      return set.getOrder().emptyDepset();
+    }
     return new Depset(elemType, set);
   }
 
@@ -280,15 +283,11 @@
   public static <T> NestedSet<T> noneableCast(Object x, Class<T> type, String what)
       throws EvalException {
     if (x == Starlark.NONE) {
-      @SuppressWarnings("unchecked")
-      NestedSet<T> empty = (NestedSet<T>) EMPTY;
-      return empty;
+      return NestedSetBuilder.emptySet(Order.STABLE_ORDER);
     }
     return cast(x, type, what);
   }
 
-  private static final NestedSet<?> EMPTY = NestedSetBuilder.<Object>emptySet(Order.STABLE_ORDER);
-
   public boolean isEmpty() {
     return set.isEmpty();
   }
@@ -390,6 +389,9 @@
       }
     }
 
+    if (builder.isEmpty()) {
+      return builder.getOrder().emptyDepset();
+    }
     return new Depset(type, builder.build());
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/collect/nestedset/Order.java b/src/main/java/com/google/devtools/build/lib/collect/nestedset/Order.java
index 1a62d05..3f0ea09 100644
--- a/src/main/java/com/google/devtools/build/lib/collect/nestedset/Order.java
+++ b/src/main/java/com/google/devtools/build/lib/collect/nestedset/Order.java
@@ -112,10 +112,12 @@
 
   private final String starlarkName;
   private final NestedSet<?> emptySet;
+  private final Depset emptyDepset;
 
-  private Order(String starlarkName) {
+  Order(String starlarkName) {
     this.starlarkName = starlarkName;
     this.emptySet = new NestedSet<>(this);
+    this.emptyDepset = new Depset(Depset.ElementType.EMPTY, this.emptySet);
   }
 
   @SerializationConstant @AutoCodec.VisibleForSerialization
@@ -150,6 +152,11 @@
     return (NestedSet<E>) emptySet;
   }
 
+  /** Returns an empty depset of the given ordering. */
+  Depset emptyDepset() {
+    return emptyDepset;
+  }
+
   public String getStarlarkName() {
     return starlarkName;
   }
diff --git a/src/test/java/com/google/devtools/build/lib/collect/nestedset/DepsetTest.java b/src/test/java/com/google/devtools/build/lib/collect/nestedset/DepsetTest.java
index cc6d597..a213985 100644
--- a/src/test/java/com/google/devtools/build/lib/collect/nestedset/DepsetTest.java
+++ b/src/test/java/com/google/devtools/build/lib/collect/nestedset/DepsetTest.java
@@ -404,4 +404,17 @@
                 + " NoneType'",
             "depset(direct='hello')");
   }
+
+  @Test
+  public void testEmptyDepsetInternedPerOrder() throws Exception {
+    ev.exec(
+        "stable1 = depset()",
+        "stable2 = depset()",
+        "preorder1 = depset(order = 'preorder')",
+        "preorder2 = depset(order = 'preorder')");
+    assertThat(ev.lookup("stable1")).isSameInstanceAs(ev.lookup("stable2"));
+    assertThat(ev.lookup("preorder1")).isSameInstanceAs(ev.lookup("preorder2"));
+    assertThat(ev.lookup("stable1")).isNotSameInstanceAs(ev.lookup("preorder1"));
+    assertThat(ev.lookup("stable2")).isNotSameInstanceAs(ev.lookup("preorder2"));
+  }
 }