diff --git a/ui/build/ninja.go b/ui/build/ninja.go
index 835f820..cb41579 100644
--- a/ui/build/ninja.go
+++ b/ui/build/ninja.go
@@ -59,6 +59,7 @@
 		"-w", "missingdepfile=err")
 
 	cmd := Command(ctx, config, "ninja", executable, args...)
+	cmd.Sandbox = ninjaSandbox
 	if config.HasKatiSuffix() {
 		cmd.Environment.AppendFromKati(config.KatiEnvFile())
 	}
diff --git a/ui/build/sandbox_darwin.go b/ui/build/sandbox_darwin.go
index 7e75167..43c5480 100644
--- a/ui/build/sandbox_darwin.go
+++ b/ui/build/sandbox_darwin.go
@@ -21,12 +21,12 @@
 type Sandbox string
 
 const (
-	noSandbox            = ""
-	globalSandbox        = "build/soong/ui/build/sandbox/darwin/global.sb"
-	dumpvarsSandbox      = globalSandbox
-	soongSandbox         = globalSandbox
-	katiSandbox          = globalSandbox
-	katiCleanSpecSandbox = globalSandbox
+	noSandbox       = ""
+	globalSandbox   = "build/soong/ui/build/sandbox/darwin/global.sb"
+	dumpvarsSandbox = globalSandbox
+	soongSandbox    = globalSandbox
+	katiSandbox     = globalSandbox
+	ninjaSandbox    = noSandbox
 )
 
 var sandboxExecPath string
diff --git a/ui/build/sandbox_linux.go b/ui/build/sandbox_linux.go
index f2bfac2..b87637f 100644
--- a/ui/build/sandbox_linux.go
+++ b/ui/build/sandbox_linux.go
@@ -14,20 +14,154 @@
 
 package build
 
-type Sandbox bool
-
-const (
-	noSandbox            = false
-	globalSandbox        = false
-	dumpvarsSandbox      = false
-	soongSandbox         = false
-	katiSandbox          = false
-	katiCleanSpecSandbox = false
+import (
+	"bytes"
+	"os"
+	"os/exec"
+	"os/user"
+	"strings"
+	"sync"
 )
 
+type Sandbox struct {
+	Enabled              bool
+	DisableWhenUsingGoma bool
+}
+
+var (
+	noSandbox    = Sandbox{}
+	basicSandbox = Sandbox{
+		Enabled: true,
+	}
+
+	dumpvarsSandbox = basicSandbox
+	katiSandbox     = basicSandbox
+	soongSandbox    = basicSandbox
+	ninjaSandbox    = Sandbox{
+		Enabled:              true,
+		DisableWhenUsingGoma: true,
+	}
+)
+
+const nsjailPath = "prebuilts/build-tools/linux-x86/bin/nsjail"
+
+var sandboxConfig struct {
+	once sync.Once
+
+	working bool
+	group   string
+}
+
 func (c *Cmd) sandboxSupported() bool {
-	return false
+	if !c.Sandbox.Enabled {
+		return false
+	}
+
+	// Goma is incompatible with PID namespaces and Mount namespaces. b/122767582
+	if c.Sandbox.DisableWhenUsingGoma && c.config.UseGoma() {
+		return false
+	}
+
+	sandboxConfig.once.Do(func() {
+		sandboxConfig.group = "nogroup"
+		if _, err := user.LookupGroup(sandboxConfig.group); err != nil {
+			sandboxConfig.group = "nobody"
+		}
+
+		cmd := exec.CommandContext(c.ctx.Context, nsjailPath,
+			"-H", "android-build",
+			"-e",
+			"-u", "nobody",
+			"-g", sandboxConfig.group,
+			"-B", "/",
+			"--disable_clone_newcgroup",
+			"--",
+			"/bin/bash", "-c", `if [ $(hostname) == "android-build" ]; then echo "Android" "Success"; else echo Failure; fi`)
+		cmd.Env = c.config.Environment().Environ()
+
+		c.ctx.Verboseln(cmd.Args)
+		data, err := cmd.CombinedOutput()
+		if err == nil && bytes.Contains(data, []byte("Android Success")) {
+			sandboxConfig.working = true
+			return
+		}
+
+		c.ctx.Println("Build sandboxing disabled due to nsjail error. This may become fatal in the future.")
+		c.ctx.Println("Please let us know why nsjail doesn't work in your environment at:")
+		c.ctx.Println("  https://groups.google.com/forum/#!forum/android-building")
+		c.ctx.Println("  https://issuetracker.google.com/issues/new?component=381517")
+
+		for _, line := range strings.Split(strings.TrimSpace(string(data)), "\n") {
+			c.ctx.Verboseln(line)
+		}
+
+		if err == nil {
+			c.ctx.Verboseln("nsjail exited successfully, but without the correct output")
+		} else if e, ok := err.(*exec.ExitError); ok {
+			c.ctx.Verbosef("nsjail failed with %v", e.ProcessState.String())
+		} else {
+			c.ctx.Verbosef("nsjail failed with %v", err)
+		}
+	})
+
+	return sandboxConfig.working
 }
 
 func (c *Cmd) wrapSandbox() {
+	wd, _ := os.Getwd()
+
+	sandboxArgs := []string{
+		// The executable to run
+		"-x", c.Path,
+
+		// Set the hostname to something consistent
+		"-H", "android-build",
+
+		// Use the current working dir
+		"--cwd", wd,
+
+		// No time limit
+		"-t", "0",
+
+		// Keep all environment variables, we already filter them out
+		// in soong_ui
+		"-e",
+
+		// Use a consistent user & group.
+		// Note that these are mapped back to the real UID/GID when
+		// doing filesystem operations, so they're rather arbitrary.
+		"-u", "nobody",
+		"-g", sandboxConfig.group,
+
+		// Set high values, as nsjail uses low defaults.
+		"--rlimit_as", "soft",
+		"--rlimit_core", "soft",
+		"--rlimit_cpu", "soft",
+		"--rlimit_fsize", "soft",
+		"--rlimit_nofile", "soft",
+
+		// For now, just map everything. Eventually we should limit this, especially to make most things readonly.
+		"-B", "/",
+
+		// Enable networking for now. TODO: remove
+		"-N",
+
+		// Disable newcgroup for now, since it may require newer kernels
+		// TODO: try out cgroups
+		"--disable_clone_newcgroup",
+
+		// Only log important warnings / errors
+		"-q",
+
+		// Stop parsing arguments
+		"--",
+	}
+	c.Args = append(sandboxArgs, c.Args[1:]...)
+	c.Path = nsjailPath
+
+	env := Environment(c.Env)
+	if _, hasUser := env.Get("USER"); hasUser {
+		env.Set("USER", "nobody")
+	}
+	c.Env = []string(env)
 }