diff --git a/src/main/java/com/google/devtools/build/lib/buildtool/ExecutionTool.java b/src/main/java/com/google/devtools/build/lib/buildtool/ExecutionTool.java
index 7bf45c4..66275dc 100644
--- a/src/main/java/com/google/devtools/build/lib/buildtool/ExecutionTool.java
+++ b/src/main/java/com/google/devtools/build/lib/buildtool/ExecutionTool.java
@@ -208,6 +208,10 @@
     this.runtime = runtime;
     this.request = request;
 
+    // Create tools before getting the strategies from the modules as some of them need tools to
+    // determine whether the host actually supports certain strategies (e.g. sandboxing).
+    createToolsSymlinks();
+
     this.actionContextProviders =
         getActionContextProvidersFromModules(
             new FilesetActionContextImpl.Provider(
@@ -314,7 +318,6 @@
   }
 
   void init() throws ExecutorInitException {
-    createToolsSymlinks();
     getExecutor();
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/sandbox/BUILD b/src/main/java/com/google/devtools/build/lib/sandbox/BUILD
index febc5d7..53b707f 100644
--- a/src/main/java/com/google/devtools/build/lib/sandbox/BUILD
+++ b/src/main/java/com/google/devtools/build/lib/sandbox/BUILD
@@ -13,6 +13,7 @@
         "//src/main/java:buildtool-runtime",
         "//src/main/java:common",
         "//src/main/java:events",
+        "//src/main/java:options",
         "//src/main/java:packages",
         "//src/main/java:shell",
         "//src/main/java:unix",
diff --git a/src/main/java/com/google/devtools/build/lib/sandbox/NamespaceSandboxRunner.java b/src/main/java/com/google/devtools/build/lib/sandbox/NamespaceSandboxRunner.java
index b68590c..6866312 100644
--- a/src/main/java/com/google/devtools/build/lib/sandbox/NamespaceSandboxRunner.java
+++ b/src/main/java/com/google/devtools/build/lib/sandbox/NamespaceSandboxRunner.java
@@ -18,10 +18,13 @@
 import com.google.common.collect.ImmutableMultimap;
 import com.google.common.io.Files;
 import com.google.devtools.build.lib.actions.ActionInput;
+import com.google.devtools.build.lib.analysis.config.BinTools;
+import com.google.devtools.build.lib.runtime.BlazeRuntime;
 import com.google.devtools.build.lib.shell.Command;
 import com.google.devtools.build.lib.shell.CommandException;
 import com.google.devtools.build.lib.unix.FilesystemUtils;
 import com.google.devtools.build.lib.util.io.FileOutErr;
+import com.google.devtools.build.lib.util.io.OutErr;
 import com.google.devtools.build.lib.vfs.FileSystemUtils;
 import com.google.devtools.build.lib.vfs.Path;
 import com.google.devtools.build.lib.vfs.PathFragment;
@@ -52,6 +55,33 @@
     this.debug = debug;
   }
 
+  static boolean isSupported(BlazeRuntime runtime) {
+    Path execRoot = runtime.getExecRoot();
+    OutErr outErr = runtime.getReporter().getOutErr();
+    BinTools binTools = runtime.getBinTools();
+
+    List<String> args = new ArrayList<>();
+    args.add(execRoot.getRelative(binTools.getExecPath("namespace-sandbox")).getPathString());
+    args.add("-C");
+
+    ImmutableMap<String, String> env = ImmutableMap.of();
+    File cwd = execRoot.getPathFile();
+
+    Command cmd = new Command(args.toArray(new String[0]), env, cwd);
+    try {
+      cmd.execute(
+          /* stdin */ new byte[] {},
+          Command.NO_OBSERVER,
+          outErr.getOutputStream(),
+          outErr.getErrorStream(),
+          /* killSubprocessOnInterrupt */ true);
+    } catch (CommandException e) {
+      return false;
+    }
+
+    return true;
+  }
+
   /**
    * Runs given
    *
diff --git a/src/main/java/com/google/devtools/build/lib/sandbox/SandboxModule.java b/src/main/java/com/google/devtools/build/lib/sandbox/SandboxModule.java
index bc8785b..0821786 100644
--- a/src/main/java/com/google/devtools/build/lib/sandbox/SandboxModule.java
+++ b/src/main/java/com/google/devtools/build/lib/sandbox/SandboxModule.java
@@ -20,9 +20,12 @@
 import com.google.devtools.build.lib.actions.ActionContextProvider;
 import com.google.devtools.build.lib.buildtool.BuildRequest;
 import com.google.devtools.build.lib.buildtool.buildevent.BuildStartingEvent;
+import com.google.devtools.build.lib.events.Event;
 import com.google.devtools.build.lib.runtime.BlazeModule;
 import com.google.devtools.build.lib.runtime.BlazeRuntime;
 import com.google.devtools.build.lib.runtime.Command;
+import com.google.devtools.build.lib.util.OS;
+import com.google.devtools.common.options.OptionsBase;
 
 import java.util.concurrent.ExecutorService;
 import java.util.concurrent.Executors;
@@ -35,16 +38,58 @@
   private final ExecutorService backgroundWorkers = Executors.newCachedThreadPool();
   private BuildRequest buildRequest;
   private BlazeRuntime runtime;
+  private Boolean sandboxingSupported = null;
+
+  public static final String SANDBOX_NOT_SUPPORTED_MESSAGE =
+      "Sandboxed execution is not supported on your system and thus hermeticity of actions cannot "
+          + "be guaranteed. See http://bazel.io/docs/bazel-user-manual.html#sandboxing for more "
+          + "information";
 
   @Override
   public Iterable<ActionContextProvider> getActionContextProviders() {
-    return ImmutableList.<ActionContextProvider>of(
-        new SandboxActionContextProvider(runtime, buildRequest, backgroundWorkers));
+    Preconditions.checkNotNull(buildRequest);
+    Preconditions.checkNotNull(runtime);
+
+    // Cache
+    if (sandboxingSupported == null) {
+      sandboxingSupported = NamespaceSandboxRunner.isSupported(runtime);
+    }
+
+    if (sandboxingSupported) {
+      return ImmutableList.<ActionContextProvider>of(
+          new SandboxActionContextProvider(runtime, buildRequest, backgroundWorkers));
+    }
+
+    // For now, sandboxing is only supported on Linux and there's not much point in showing a scary
+    // warning to the user if they can't do anything about it.
+    if (!buildRequest.getOptions(SandboxOptions.class).ignoreUnsupportedSandboxing
+        && OS.getCurrent() == OS.LINUX) {
+      runtime.getReporter().handle(Event.warn(SANDBOX_NOT_SUPPORTED_MESSAGE));
+    }
+
+    return ImmutableList.of();
   }
 
   @Override
   public Iterable<ActionContextConsumer> getActionContextConsumers() {
-    return ImmutableList.<ActionContextConsumer>of(new SandboxActionContextConsumer());
+    Preconditions.checkNotNull(runtime);
+
+    if (sandboxingSupported == null) {
+      sandboxingSupported = NamespaceSandboxRunner.isSupported(runtime);
+    }
+
+    if (sandboxingSupported) {
+      return ImmutableList.<ActionContextConsumer>of(new SandboxActionContextConsumer());
+    }
+
+    return ImmutableList.of();
+  }
+
+  @Override
+  public Iterable<Class<? extends OptionsBase>> getCommandOptions(Command command) {
+    return command.builds()
+        ? ImmutableList.<Class<? extends OptionsBase>>of(SandboxOptions.class)
+        : ImmutableList.<Class<? extends OptionsBase>>of();
   }
 
   @Override
diff --git a/src/main/java/com/google/devtools/build/lib/sandbox/SandboxOptions.java b/src/main/java/com/google/devtools/build/lib/sandbox/SandboxOptions.java
new file mode 100644
index 0000000..ad4fa50
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/sandbox/SandboxOptions.java
@@ -0,0 +1,31 @@
+// Copyright 2015 Google Inc. 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.sandbox;
+
+import com.google.devtools.common.options.Option;
+import com.google.devtools.common.options.OptionsBase;
+
+/**
+ * Options for sandboxed execution.
+ */
+public class SandboxOptions extends OptionsBase {
+
+  @Option(
+    name = "ignore_unsupported_sandboxing",
+    defaultValue = "false",
+    category = "strategy",
+    help = "Do not print a warning when sandboxed execution is not supported on this system."
+  )
+  public boolean ignoreUnsupportedSandboxing;
+}
diff --git a/src/main/tools/namespace-sandbox-dummy.c b/src/main/tools/namespace-sandbox-dummy.c
index dd9f47f..3693c8d 100644
--- a/src/main/tools/namespace-sandbox-dummy.c
+++ b/src/main/tools/namespace-sandbox-dummy.c
@@ -19,6 +19,6 @@
 // platforms (if we didn't have this file, it would fail with a non-informative
 // message)
 
-int main() {
-  return 0;
+int main(int argc, char *argv[]) {
+  return 1;
 }
diff --git a/src/main/tools/namespace-sandbox.c b/src/main/tools/namespace-sandbox.c
index 9b484d3..33cacb7 100644
--- a/src/main/tools/namespace-sandbox.c
+++ b/src/main/tools/namespace-sandbox.c
@@ -29,6 +29,7 @@
 #include <sys/stat.h>
 #include <sys/syscall.h>
 #include <sys/types.h>
+#include <sys/wait.h>
 #include <unistd.h>
 
 #include "process-tools.h"
@@ -54,16 +55,48 @@
   double timeout_secs;     // How long to wait before killing the child (-T)
   double kill_delay_secs;  // How long to wait before sending SIGKILL in case of
                            // timeout (-t)
-  const char *stdout_path;       // Where to redirect stdout (-l)
-  const char *stderr_path;       // Where to redirect stderr (-L)
-  char *const *args;             // Command to run (--)
-  const char *sandbox_root;      // Sandbox root (-S)
-  const char *working_dir;       // Working directory (-W)
-  char **mount_sources;    // Map of directories to mount, from
-  char **mount_targets;    // sources -> targets (-m)
-  int num_mounts;          // How many mounts were specified
+  const char *stdout_path;   // Where to redirect stdout (-l)
+  const char *stderr_path;   // Where to redirect stderr (-L)
+  char *const *args;         // Command to run (--)
+  const char *sandbox_root;  // Sandbox root (-S)
+  const char *working_dir;   // Working directory (-W)
+  char **mount_sources;      // Map of directories to mount, from
+  char **mount_targets;      // sources -> targets (-m)
+  int num_mounts;            // How many mounts were specified
 };
 
+// Child function used by CheckNamespacesSupported() in call to clone().
+static int CheckNamespacesSupportedChild(void *arg) { return 0; }
+
+// Check whether the required namespaces are supported.
+static int CheckNamespacesSupported() {
+  const int stackSize = 1024 * 1024;
+  char *stack;
+  char *stackTop;
+  pid_t pid;
+
+  // Allocate stack for child.
+  stack = malloc(stackSize);
+  if (stack == NULL) {
+    DIE("malloc failed\n");
+  }
+
+  // Assume stack grows downward.
+  stackTop = stack + stackSize;
+
+  // Create child with own namespaces. We use clone() instead of unshare() here
+  // because of the kernel bug (ref. CreateNamespaces) that lets unshare fail
+  // sometimes. As this check has to run as fast as possible, we can't afford to
+  // spend time sleeping and retrying here until it eventually works (or not).
+  CHECK_CALL(pid = clone(CheckNamespacesSupportedChild, stackTop,
+                         CLONE_NEWUSER | CLONE_NEWNS | CLONE_NEWUTS |
+                             CLONE_NEWIPC | SIGCHLD,
+                         NULL));
+  CHECK_CALL(waitpid(pid, NULL, 0));
+
+  return EXIT_SUCCESS;
+}
+
 // Print out a usage error. argc and argv are the argument counter and vector,
 // fmt is a format,
 // string for the error message to print.
@@ -112,8 +145,12 @@
   extern int optind, optopt;
   int c;
 
-  while ((c = getopt(argc, argv, ":DS:W:t:T:M:m:l:L:")) != -1) {
+  while ((c = getopt(argc, argv, ":CDS:W:t:T:M:m:l:L:")) != -1) {
     switch (c) {
+      case 'C':
+        // Shortcut for the "does this system support sandboxing" check.
+        exit(CheckNamespacesSupported());
+        break;
       case 'S':
         if (opt->sandbox_root == NULL) {
           opt->sandbox_root = optarg;
@@ -212,9 +249,10 @@
 }
 
 static void CreateNamespaces() {
-  // This weird workaround is necessary due to unshare seldomly failing with EINVAL due to a race
-  // condition in the Linux kernel (see https://lkml.org/lkml/2015/7/28/833).
-  // An alternative would be to use clone/waitpid instead.
+  // This weird workaround is necessary due to unshare seldomly failing with
+  // EINVAL due to a race condition in the Linux kernel (see
+  // https://lkml.org/lkml/2015/7/28/833). An alternative would be to use
+  // clone/waitpid instead.
   int delay = 1;
   int tries = 0;
   const int max_tries = 100;
@@ -251,7 +289,7 @@
 static void SetupDevices() {
   CHECK_CALL(mkdir("dev", 0755));
   const char *devs[] = {"/dev/null", "/dev/random", "/dev/urandom", "/dev/zero",
-                  NULL};
+                        NULL};
   for (int i = 0; devs[i] != NULL; i++) {
     CreateFile(devs[i] + 1);
     CHECK_CALL(mount(devs[i], devs[i] + 1, NULL, MS_BIND, NULL));
@@ -321,14 +359,16 @@
   // Make sure the home directory exists and is writable.
   const char *homedir;
   if ((homedir = getenv("HOME")) == NULL) {
-      homedir = getpwuid(getuid())->pw_dir;
+    homedir = getpwuid(getuid())->pw_dir;
   }
 
   if (homedir[0] != '/') {
-    DIE("Home directory of user nobody must be an absolute path, but is %s", homedir);
+    DIE("Home directory of user nobody must be an absolute path, but is %s",
+        homedir);
   }
 
-  char *homedir_absolute = malloc(strlen(opt->sandbox_root) + strlen(homedir) + 1);
+  char *homedir_absolute =
+      malloc(strlen(opt->sandbox_root) + strlen(homedir) + 1);
   strcpy(homedir_absolute, opt->sandbox_root);
   strcat(homedir_absolute, homedir);
 
@@ -381,9 +421,9 @@
   // Set group and user mapping from outer namespace to inner:
   // No changes in the parent, be nobody in the child.
   //
-  // We can't be root in the child, because some code may assume that running as root grants it
-  // certain capabilities that it doesn't in fact have. It's safer to let the child think that it
-  // is just a normal user.
+  // We can't be root in the child, because some code may assume that running as
+  // root grants it certain capabilities that it doesn't in fact have. It's
+  // safer to let the child think that it is just a normal user.
   CHECK_CALL(WriteFile("/proc/self/uid_map", "%d %d 1\n", kNobodyUid, uid));
   CHECK_CALL(WriteFile("/proc/self/gid_map", "%d %d 1\n", kNobodyGid, gid));