diff --git a/site/en/run/scripts.md b/site/en/run/scripts.md
index dc17707..773baa1 100644
--- a/site/en/run/scripts.md
+++ b/site/en/run/scripts.md
@@ -57,6 +57,7 @@
 -   `36` - Local Environmental Issue, suspected permanent.
 -   `37` - Unhandled Exception / Internal Bazel Error.
 -   `38` - Reserved for Google-internal use.
+-   `39` - Blobs required by Bazel are evicted from Remote Cache.
 -   `41-44` - Reserved for Google-internal use.
 -   `45` - Error publishing results to the Build Event Service.
 -   `47` - Reserved for Google-internal use.
diff --git a/src/main/java/com/google/devtools/build/lib/exec/SpawnRunner.java b/src/main/java/com/google/devtools/build/lib/exec/SpawnRunner.java
index 0b2c8aa..e4b6c31 100644
--- a/src/main/java/com/google/devtools/build/lib/exec/SpawnRunner.java
+++ b/src/main/java/com/google/devtools/build/lib/exec/SpawnRunner.java
@@ -161,7 +161,7 @@
      * @see #prefetchInputs()
      */
     default void prefetchInputsAndWait()
-        throws IOException, InterruptedException, ForbiddenActionInputException {
+        throws IOException, ExecException, InterruptedException, ForbiddenActionInputException {
       ListenableFuture<Void> future = prefetchInputs();
       try (SilentCloseable s =
           Profiler.instance().profile(ProfilerTask.REMOTE_DOWNLOAD, "stage remote inputs")) {
@@ -170,6 +170,7 @@
         Throwable cause = e.getCause();
         if (cause != null) {
           throwIfInstanceOf(cause, IOException.class);
+          throwIfInstanceOf(cause, ExecException.class);
           throwIfInstanceOf(cause, ForbiddenActionInputException.class);
           throwIfInstanceOf(cause, RuntimeException.class);
         }
diff --git a/src/main/java/com/google/devtools/build/lib/remote/BUILD b/src/main/java/com/google/devtools/build/lib/remote/BUILD
index b192c95..b7de294 100644
--- a/src/main/java/com/google/devtools/build/lib/remote/BUILD
+++ b/src/main/java/com/google/devtools/build/lib/remote/BUILD
@@ -92,7 +92,6 @@
         "//src/main/java/com/google/devtools/build/lib/remote/options",
         "//src/main/java/com/google/devtools/build/lib/remote/util",
         "//src/main/java/com/google/devtools/build/lib/remote/zstd",
-        "//src/main/java/com/google/devtools/build/lib/sandbox:sandbox_helpers",
         "//src/main/java/com/google/devtools/build/lib/skyframe:mutable_supplier",
         "//src/main/java/com/google/devtools/build/lib/skyframe:tree_artifact_value",
         "//src/main/java/com/google/devtools/build/lib/util",
diff --git a/src/main/java/com/google/devtools/build/lib/remote/RemoteActionInputFetcher.java b/src/main/java/com/google/devtools/build/lib/remote/RemoteActionInputFetcher.java
index b0251f7..ff625eb 100644
--- a/src/main/java/com/google/devtools/build/lib/remote/RemoteActionInputFetcher.java
+++ b/src/main/java/com/google/devtools/build/lib/remote/RemoteActionInputFetcher.java
@@ -20,15 +20,18 @@
 import com.google.common.base.Preconditions;
 import com.google.common.collect.ImmutableList;
 import com.google.common.util.concurrent.ListenableFuture;
+import com.google.devtools.build.lib.actions.EnvironmentalExecException;
 import com.google.devtools.build.lib.actions.FileArtifactValue;
 import com.google.devtools.build.lib.actions.cache.VirtualActionInput;
 import com.google.devtools.build.lib.events.Reporter;
 import com.google.devtools.build.lib.remote.common.BulkTransferException;
-import com.google.devtools.build.lib.remote.common.CacheNotFoundException;
 import com.google.devtools.build.lib.remote.common.RemoteActionExecutionContext;
 import com.google.devtools.build.lib.remote.util.DigestUtil;
 import com.google.devtools.build.lib.remote.util.TempPathGenerator;
 import com.google.devtools.build.lib.remote.util.TracingMetadataUtils;
+import com.google.devtools.build.lib.server.FailureDetails;
+import com.google.devtools.build.lib.server.FailureDetails.FailureDetail;
+import com.google.devtools.build.lib.server.FailureDetails.Spawn.Code;
 import com.google.devtools.build.lib.vfs.OutputPermissions;
 import com.google.devtools.build.lib.vfs.Path;
 import com.google.devtools.build.lib.vfs.PathFragment;
@@ -47,6 +50,7 @@
   private final String buildRequestId;
   private final String commandId;
   private final RemoteCache remoteCache;
+  private final boolean useNewExitCodeForLostInputs;
 
   RemoteActionInputFetcher(
       Reporter reporter,
@@ -56,11 +60,13 @@
       Path execRoot,
       TempPathGenerator tempPathGenerator,
       ImmutableList<Pattern> patternsToDownload,
-      OutputPermissions outputPermissions) {
+      OutputPermissions outputPermissions,
+      boolean useNewExitCodeForLostInputs) {
     super(reporter, execRoot, tempPathGenerator, patternsToDownload, outputPermissions);
     this.buildRequestId = Preconditions.checkNotNull(buildRequestId);
     this.commandId = Preconditions.checkNotNull(commandId);
     this.remoteCache = Preconditions.checkNotNull(remoteCache);
+    this.useNewExitCodeForLostInputs = useNewExitCodeForLostInputs;
   }
 
   @Override
@@ -96,19 +102,18 @@
   protected Completable onErrorResumeNext(Throwable error) {
     if (error instanceof BulkTransferException) {
       if (((BulkTransferException) error).onlyCausedByCacheNotFoundException()) {
-        BulkTransferException bulkAnnotatedException = new BulkTransferException();
-        for (Throwable t : error.getSuppressed()) {
-          IOException annotatedException =
-              new IOException(
-                  String.format(
-                      "Failed to fetch file with hash '%s' because it does not"
-                          + " exist remotely. --remote_download_outputs=minimal"
-                          + " does not work if your remote cache evicts files"
-                          + " during builds.",
-                      ((CacheNotFoundException) t).getMissingDigest().getHash()));
-          bulkAnnotatedException.add(annotatedException);
-        }
-        error = bulkAnnotatedException;
+        var code =
+            useNewExitCodeForLostInputs ? Code.REMOTE_CACHE_EVICTED : Code.REMOTE_CACHE_FAILED;
+        error =
+            new EnvironmentalExecException(
+                (BulkTransferException) error,
+                FailureDetail.newBuilder()
+                    .setMessage(
+                        "Failed to fetch blobs because they do not exist remotely."
+                            + " Build without the Bytes does not work if your remote"
+                            + " cache evicts blobs during builds")
+                    .setSpawn(FailureDetails.Spawn.newBuilder().setCode(code))
+                    .build());
       }
     }
     return Completable.error(error);
diff --git a/src/main/java/com/google/devtools/build/lib/remote/RemoteModule.java b/src/main/java/com/google/devtools/build/lib/remote/RemoteModule.java
index 4e32ee0..5e425d0 100644
--- a/src/main/java/com/google/devtools/build/lib/remote/RemoteModule.java
+++ b/src/main/java/com/google/devtools/build/lib/remote/RemoteModule.java
@@ -983,7 +983,8 @@
               env.getExecRoot(),
               tempPathGenerator,
               patternsToDownload,
-              outputPermissions);
+              outputPermissions,
+              remoteOptions.useNewExitCodeForLostInputs);
       env.getEventBus().register(actionInputFetcher);
       builder.setActionInputPrefetcher(actionInputFetcher);
       remoteOutputService.setActionInputFetcher(actionInputFetcher);
diff --git a/src/main/java/com/google/devtools/build/lib/remote/options/RemoteOptions.java b/src/main/java/com/google/devtools/build/lib/remote/options/RemoteOptions.java
index c812a42..ba84883 100644
--- a/src/main/java/com/google/devtools/build/lib/remote/options/RemoteOptions.java
+++ b/src/main/java/com/google/devtools/build/lib/remote/options/RemoteOptions.java
@@ -658,6 +658,17 @@
               + "cache misses and retries.")
   public boolean remoteDiscardMerkleTrees;
 
+  @Option(
+      name = "incompatible_remote_use_new_exit_code_for_lost_inputs",
+      defaultValue = "false",
+      documentationCategory = OptionDocumentationCategory.REMOTE,
+      effectTags = {OptionEffectTag.UNKNOWN},
+      metadataTags = {OptionMetadataTag.INCOMPATIBLE_CHANGE},
+      help =
+          "If set to true, Bazel will use new exit code 39 instead of 34 if remote cache evicts"
+              + " blobs during the build.")
+  public boolean useNewExitCodeForLostInputs;
+
   // The below options are not configurable by users, only tests.
   // This is part of the effort to reduce the overall number of flags.
 
diff --git a/src/main/java/com/google/devtools/build/lib/util/ExitCode.java b/src/main/java/com/google/devtools/build/lib/util/ExitCode.java
index f91fffa..24d51c5 100644
--- a/src/main/java/com/google/devtools/build/lib/util/ExitCode.java
+++ b/src/main/java/com/google/devtools/build/lib/util/ExitCode.java
@@ -65,6 +65,8 @@
       ExitCode.createInfrastructureFailure(37, "BLAZE_INTERNAL_ERROR");
   public static final ExitCode TRANSIENT_BUILD_EVENT_SERVICE_UPLOAD_ERROR =
       ExitCode.createInfrastructureFailure(38, "PUBLISH_ERROR");
+  public static final ExitCode REMOTE_CACHE_EVICTED =
+      ExitCode.createInfrastructureFailure(39, "REMOTE_CACHE_EVICTED");
   public static final ExitCode PERSISTENT_BUILD_EVENT_SERVICE_UPLOAD_ERROR =
       ExitCode.create(45, "PERSISTENT_BUILD_EVENT_SERVICE_UPLOAD_ERROR");
   public static final ExitCode EXTERNAL_DEPS_ERROR = ExitCode.create(48, "EXTERNAL_DEPS_ERROR");
diff --git a/src/main/protobuf/failure_details.proto b/src/main/protobuf/failure_details.proto
index 82e7688..21bf208 100644
--- a/src/main/protobuf/failure_details.proto
+++ b/src/main/protobuf/failure_details.proto
@@ -226,6 +226,7 @@
     //   refactored to prohibit undetailed failures
     UNSPECIFIED_EXECUTION_FAILURE = 12 [(metadata) = { exit_code: 1 }];
     FORBIDDEN_INPUT = 13 [(metadata) = { exit_code: 1 }];
+    REMOTE_CACHE_EVICTED = 14 [(metadata) = { exit_code: 39 }];
   }
   Code code = 1;
 
diff --git a/src/test/java/com/google/devtools/build/lib/remote/ActionInputPrefetcherTestBase.java b/src/test/java/com/google/devtools/build/lib/remote/ActionInputPrefetcherTestBase.java
index 2b0124d..912c269 100644
--- a/src/test/java/com/google/devtools/build/lib/remote/ActionInputPrefetcherTestBase.java
+++ b/src/test/java/com/google/devtools/build/lib/remote/ActionInputPrefetcherTestBase.java
@@ -37,12 +37,12 @@
 import com.google.devtools.build.lib.actions.Artifact.TreeFileArtifact;
 import com.google.devtools.build.lib.actions.ArtifactRoot;
 import com.google.devtools.build.lib.actions.ArtifactRoot.RootType;
+import com.google.devtools.build.lib.actions.ExecException;
 import com.google.devtools.build.lib.actions.FileArtifactValue;
 import com.google.devtools.build.lib.actions.FileArtifactValue.RemoteFileArtifactValue;
 import com.google.devtools.build.lib.actions.MetadataProvider;
 import com.google.devtools.build.lib.actions.util.ActionsTestUtil;
 import com.google.devtools.build.lib.clock.JavaClock;
-import com.google.devtools.build.lib.remote.common.BulkTransferException;
 import com.google.devtools.build.lib.remote.util.StaticMetadataProvider;
 import com.google.devtools.build.lib.remote.util.TempPathGenerator;
 import com.google.devtools.build.lib.skyframe.TreeArtifactValue;
@@ -160,7 +160,8 @@
   protected abstract AbstractActionInputPrefetcher createPrefetcher(Map<HashCode, byte[]> cas);
 
   @Test
-  public void prefetchFiles_fileExists_doNotDownload() throws IOException, InterruptedException {
+  public void prefetchFiles_fileExists_doNotDownload()
+      throws IOException, ExecException, InterruptedException {
     Map<ActionInput, FileArtifactValue> metadata = new HashMap<>();
     Map<HashCode, byte[]> cas = new HashMap<>();
     Artifact a = createRemoteArtifact("file", "hello world", metadata, cas);
@@ -177,7 +178,7 @@
 
   @Test
   public void prefetchFiles_fileExistsButContentMismatches_download()
-      throws IOException, InterruptedException {
+      throws IOException, ExecException, InterruptedException {
     Map<ActionInput, FileArtifactValue> metadata = new HashMap<>();
     Map<HashCode, byte[]> cas = new HashMap<>();
     Artifact a = createRemoteArtifact("file", "hello world remote", metadata, cas);
@@ -304,7 +305,7 @@
     AbstractActionInputPrefetcher prefetcher = createPrefetcher(new HashMap<>());
 
     assertThrows(
-        BulkTransferException.class,
+        Exception.class,
         () -> wait(prefetcher.prefetchFiles(ImmutableList.of(a), metadataProvider)));
 
     assertThat(prefetcher.downloadedFiles()).isEmpty();
@@ -347,7 +348,7 @@
             () -> {
               try {
                 wait(prefetcher.prefetchFiles(ImmutableList.of(artifact), metadataProvider));
-              } catch (IOException | InterruptedException ignored) {
+              } catch (IOException | ExecException | InterruptedException ignored) {
                 // do nothing
               }
             });
@@ -357,7 +358,7 @@
             () -> {
               try {
                 wait(prefetcher.prefetchFiles(ImmutableList.of(artifact), metadataProvider));
-              } catch (IOException | InterruptedException ignored) {
+              } catch (IOException | ExecException | InterruptedException ignored) {
                 // do nothing
               }
             });
@@ -394,7 +395,7 @@
             () -> {
               try {
                 wait(prefetcher.prefetchFiles(ImmutableList.of(artifact), metadataProvider));
-              } catch (IOException | InterruptedException ignored) {
+              } catch (IOException | ExecException | InterruptedException ignored) {
                 // do nothing
               }
             });
@@ -406,7 +407,7 @@
               try {
                 wait(prefetcher.prefetchFiles(ImmutableList.of(artifact), metadataProvider));
                 successful.set(true);
-              } catch (IOException | InterruptedException ignored) {
+              } catch (IOException | ExecException | InterruptedException ignored) {
                 // do nothing
               }
             });
@@ -489,13 +490,14 @@
   }
 
   protected static void wait(ListenableFuture<Void> future)
-      throws IOException, InterruptedException {
+      throws IOException, ExecException, InterruptedException {
     try {
       future.get();
     } catch (ExecutionException e) {
       Throwable cause = e.getCause();
       if (cause != null) {
         throwIfInstanceOf(cause, IOException.class);
+        throwIfInstanceOf(cause, ExecException.class);
         throwIfInstanceOf(cause, InterruptedException.class);
         throwIfInstanceOf(cause, RuntimeException.class);
       }
diff --git a/src/test/java/com/google/devtools/build/lib/remote/BUILD b/src/test/java/com/google/devtools/build/lib/remote/BUILD
index e07286e..a65bcfc 100644
--- a/src/test/java/com/google/devtools/build/lib/remote/BUILD
+++ b/src/test/java/com/google/devtools/build/lib/remote/BUILD
@@ -162,6 +162,7 @@
         "//src/main/java/com/google/devtools/build/lib/remote",
         "//src/main/java/com/google/devtools/build/lib/standalone",
         "//src/main/java/com/google/devtools/build/lib/util:os",
+        "//src/main/java/com/google/devtools/build/lib/vfs",
         "//src/test/java/com/google/devtools/build/lib/remote/util:integration_test_utils",
         "//third_party:guava",
         "//third_party:junit4",
diff --git a/src/test/java/com/google/devtools/build/lib/remote/BuildWithoutTheBytesIntegrationTest.java b/src/test/java/com/google/devtools/build/lib/remote/BuildWithoutTheBytesIntegrationTest.java
index 8c49c36..3709b2c 100644
--- a/src/test/java/com/google/devtools/build/lib/remote/BuildWithoutTheBytesIntegrationTest.java
+++ b/src/test/java/com/google/devtools/build/lib/remote/BuildWithoutTheBytesIntegrationTest.java
@@ -30,6 +30,7 @@
 import com.google.devtools.build.lib.runtime.BuildSummaryStatsModule;
 import com.google.devtools.build.lib.standalone.StandaloneModule;
 import com.google.devtools.build.lib.util.OS;
+import com.google.devtools.build.lib.vfs.FileSystemUtils;
 import java.io.IOException;
 import org.junit.After;
 import org.junit.Test;
@@ -69,6 +70,7 @@
   @Override
   protected BlazeRuntime.Builder getRuntimeBuilder() throws Exception {
     return super.getRuntimeBuilder()
+        .addBlazeModule(new RemoteModule())
         .addBlazeModule(new BuildSummaryStatsModule())
         .addBlazeModule(new BlockWaitingModule());
   }
@@ -79,7 +81,6 @@
         .addAll(super.getSpawnModules())
         .add(new StandaloneModule())
         .add(new CredentialModule())
-        .add(new RemoteModule())
         .add(new DynamicExecutionModule())
         .build();
   }
@@ -415,4 +416,54 @@
 
     buildTarget("//a:one_local", "//a:two_local", "//a:one_remote", "//a:two_remote");
   }
+
+  @Test
+  public void remoteCacheEvictBlobs_exitWithCode39() throws Exception {
+    // Arrange: Prepare workspace and populate remote cache
+    write(
+        "a/BUILD",
+        "genrule(",
+        "  name = 'foo',",
+        "  srcs = ['foo.in'],",
+        "  outs = ['foo.out'],",
+        "  cmd = 'cat $(SRCS) > $@',",
+        ")",
+        "genrule(",
+        "  name = 'bar',",
+        "  srcs = ['foo.out', 'bar.in'],",
+        "  outs = ['bar.out'],",
+        "  cmd = 'cat $(SRCS) > $@',",
+        "  tags = ['no-remote-exec'],",
+        ")");
+    write("a/foo.in", "foo");
+    write("a/bar.in", "bar");
+
+    // Populate remote cache
+    buildTarget("//a:bar");
+    var bytes = FileSystemUtils.readContent(getOutputPath("a/foo.out"));
+    var hashCode = getDigestHashFunction().getHashFunction().hashBytes(bytes);
+    getOutputPath("a/foo.out").delete();
+    getOutputPath("a/bar.out").delete();
+    getOutputBase().getRelative("action_cache").deleteTreesBelow();
+    restartServer();
+    addOptions("--incompatible_remote_use_new_exit_code_for_lost_inputs");
+
+    // Clean build, foo.out isn't downloaded
+    buildTarget("//a:bar");
+    assertOutputDoesNotExist("a/foo.out");
+
+    // Act: Evict blobs from remote cache and do an incremental build
+    getFileSystem().getPath(worker.getCasPath().getSafePathString()).deleteTreesBelow();
+    write("a/bar.in", "updated bar");
+    var error = assertThrows(BuildFailedException.class, () -> buildTarget("//a:bar"));
+
+    // Assert: Exit code is 39
+    assertThat(error)
+        .hasMessageThat()
+        .contains(
+            "Build without the Bytes does not work if your remote cache evicts blobs"
+                + " during builds");
+    assertThat(error).hasMessageThat().contains(String.format("%s/%s", hashCode, bytes.length));
+    assertThat(error.getDetailedExitCode().getExitCode().getNumericExitCode()).isEqualTo(39);
+  }
 }
diff --git a/src/test/java/com/google/devtools/build/lib/remote/RemoteActionInputFetcherTest.java b/src/test/java/com/google/devtools/build/lib/remote/RemoteActionInputFetcherTest.java
index 5e32976..fca68db 100644
--- a/src/test/java/com/google/devtools/build/lib/remote/RemoteActionInputFetcherTest.java
+++ b/src/test/java/com/google/devtools/build/lib/remote/RemoteActionInputFetcherTest.java
@@ -14,6 +14,7 @@
 package com.google.devtools.build.lib.remote;
 
 import static com.google.common.truth.Truth.assertThat;
+import static org.junit.Assert.assertThrows;
 
 import build.bazel.remote.execution.v2.CacheCapabilities;
 import build.bazel.remote.execution.v2.Digest;
@@ -21,6 +22,10 @@
 import com.google.common.collect.Maps;
 import com.google.common.eventbus.EventBus;
 import com.google.common.hash.HashCode;
+import com.google.devtools.build.lib.actions.ActionInput;
+import com.google.devtools.build.lib.actions.Artifact;
+import com.google.devtools.build.lib.actions.ExecException;
+import com.google.devtools.build.lib.actions.FileArtifactValue;
 import com.google.devtools.build.lib.actions.MetadataProvider;
 import com.google.devtools.build.lib.actions.cache.VirtualActionInput;
 import com.google.devtools.build.lib.actions.util.ActionsTestUtil;
@@ -70,7 +75,8 @@
         execRoot,
         tempPathGenerator,
         ImmutableList.of(),
-        OutputPermissions.READONLY);
+        OutputPermissions.READONLY,
+        /* useNewExitCodeForLostInputs= */ false);
   }
 
   @Test
@@ -87,7 +93,8 @@
             execRoot,
             tempPathGenerator,
             ImmutableList.of(),
-            OutputPermissions.READONLY);
+            OutputPermissions.READONLY,
+            /* useNewExitCodeForLostInputs= */ false);
     VirtualActionInput a = ActionsTestUtil.createVirtualActionInput("file1", "hello world");
 
     // act
@@ -115,7 +122,8 @@
             execRoot,
             tempPathGenerator,
             ImmutableList.of(),
-            OutputPermissions.READONLY);
+            OutputPermissions.READONLY,
+            /* useNewExitCodeForLostInputs= */ false);
 
     // act
     wait(
@@ -127,6 +135,27 @@
     assertThat(actionInputFetcher.downloadsInProgress()).isEmpty();
   }
 
+  @Test
+  public void prefetchFiles_missingFiles_failsWithSpecificMessage() throws Exception {
+    Map<ActionInput, FileArtifactValue> metadata = new HashMap<>();
+    Artifact a = createRemoteArtifact("file1", "hello world", metadata, /* cas= */ new HashMap<>());
+    MetadataProvider metadataProvider = new StaticMetadataProvider(metadata);
+    AbstractActionInputPrefetcher prefetcher = createPrefetcher(new HashMap<>());
+
+    var error =
+        assertThrows(
+            ExecException.class,
+            () -> wait(prefetcher.prefetchFiles(ImmutableList.of(a), metadataProvider)));
+
+    assertThat(prefetcher.downloadedFiles()).isEmpty();
+    assertThat(prefetcher.downloadsInProgress()).isEmpty();
+    var m = metadataProvider.getMetadata(a);
+    var digest = DigestUtil.buildDigest(m.getDigest(), m.getSize());
+    assertThat(error)
+        .hasMessageThat()
+        .contains(String.format("%s/%s", digest.getHash(), digest.getSizeBytes()));
+  }
+
   private RemoteCache newCache(
       RemoteOptions options, DigestUtil digestUtil, Map<HashCode, byte[]> cas) {
     Map<Digest, byte[]> cacheEntries = Maps.newHashMapWithExpectedSize(cas.size());