diff --git a/android/Android.bp b/android/Android.bp
index 65332b2..cbd3459 100644
--- a/android/Android.bp
+++ b/android/Android.bp
@@ -98,6 +98,7 @@
         "apex_test.go",
         "arch_test.go",
         "bazel_handler_test.go",
+        "bazel_paths_test.go",
         "bazel_test.go",
         "config_test.go",
         "config_bp2build_test.go",
diff --git a/android/bazel_paths.go b/android/bazel_paths.go
index fa10f62..1d0a6d5 100644
--- a/android/bazel_paths.go
+++ b/android/bazel_paths.go
@@ -449,25 +449,51 @@
 	return PathForModuleObj(ctx, subdir, pathtools.ReplaceExtension(p.path, ext))
 }
 
-// PathForBazelOut returns a Path representing the paths... under an output directory dedicated to
-// bazel-owned outputs.
-func PathForBazelOut(ctx PathContext, paths ...string) BazelOutPath {
-	execRootPathComponents := append([]string{"execroot", "__main__"}, paths...)
-	execRootPath := filepath.Join(execRootPathComponents...)
-	validatedExecRootPath, err := validatePath(execRootPath)
+// PathForBazelOutRelative returns a BazelOutPath representing the path under an output directory dedicated to
+// bazel-owned outputs. Calling .Rel() on the result will give the input path as relative to the given
+// relativeRoot.
+func PathForBazelOutRelative(ctx PathContext, relativeRoot string, path string) BazelOutPath {
+	validatedPath, err := validatePath(filepath.Join("execroot", "__main__", path))
 	if err != nil {
 		reportPathError(ctx, err)
 	}
+	relativeRootPath := filepath.Join("execroot", "__main__", relativeRoot)
+	if pathComponents := strings.Split(path, "/"); len(pathComponents) >= 3 &&
+		pathComponents[0] == "bazel-out" && pathComponents[2] == "bin" {
+		// If the path starts with something like: bazel-out/linux_x86_64-fastbuild-ST-b4ef1c4402f9/bin/
+		// make it relative to that folder. bazel-out/volatile-status.txt is an example
+		// of something that starts with bazel-out but is not relative to the bin folder
+		relativeRootPath = filepath.Join("execroot", "__main__", pathComponents[0], pathComponents[1], pathComponents[2], relativeRoot)
+	}
 
-	outputPath := OutputPath{basePath{"", ""},
+	var relPath string
+	if relPath, err = filepath.Rel(relativeRootPath, validatedPath); err != nil || strings.HasPrefix(relPath, "../") {
+		// We failed to make this path relative to execroot/__main__, fall back to a non-relative path
+		// One case where this happens is when path is ../bazel_tools/something
+		relativeRootPath = ""
+		relPath = validatedPath
+	}
+
+	outputPath := OutputPath{
+		basePath{"", ""},
 		ctx.Config().soongOutDir,
-		ctx.Config().BazelContext.OutputBase()}
+		ctx.Config().BazelContext.OutputBase(),
+	}
 
 	return BazelOutPath{
-		OutputPath: outputPath.withRel(validatedExecRootPath),
+		// .withRel() appends its argument onto the current path, and only the most
+		// recently appended part is returned by outputPath.rel().
+		// So outputPath.rel() will return relPath.
+		OutputPath: outputPath.withRel(relativeRootPath).withRel(relPath),
 	}
 }
 
+// PathForBazelOut returns a BazelOutPath representing the path under an output directory dedicated to
+// bazel-owned outputs.
+func PathForBazelOut(ctx PathContext, path string) BazelOutPath {
+	return PathForBazelOutRelative(ctx, "", path)
+}
+
 // PathsForBazelOut returns a list of paths representing the paths under an output directory
 // dedicated to Bazel-owned outputs.
 func PathsForBazelOut(ctx PathContext, paths []string) Paths {
diff --git a/android/bazel_paths_test.go b/android/bazel_paths_test.go
new file mode 100644
index 0000000..b047511
--- /dev/null
+++ b/android/bazel_paths_test.go
@@ -0,0 +1,108 @@
+// Copyright 2022 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 android
+
+import (
+	"path/filepath"
+	"testing"
+)
+
+type TestBazelPathContext struct{}
+
+func (*TestBazelPathContext) Config() Config {
+	cfg := NullConfig("out", "out/soong")
+	cfg.BazelContext = MockBazelContext{
+		OutputBaseDir: "out/bazel",
+	}
+	return cfg
+}
+
+func (*TestBazelPathContext) AddNinjaFileDeps(deps ...string) {
+	panic("Unimplemented")
+}
+
+func TestPathForBazelOut(t *testing.T) {
+	ctx := &TestBazelPathContext{}
+	out := PathForBazelOut(ctx, "foo/bar/baz/boq.txt")
+	expectedPath := filepath.Join(ctx.Config().BazelContext.OutputBase(), "execroot/__main__/foo/bar/baz/boq.txt")
+	if out.String() != expectedPath {
+		t.Errorf("incorrect OutputPath: expected %q, got %q", expectedPath, out.String())
+	}
+
+	expectedRelPath := "foo/bar/baz/boq.txt"
+	if out.Rel() != expectedRelPath {
+		t.Errorf("incorrect OutputPath.Rel(): expected %q, got %q", expectedRelPath, out.Rel())
+	}
+}
+
+func TestPathForBazelOutRelative(t *testing.T) {
+	ctx := &TestBazelPathContext{}
+	out := PathForBazelOutRelative(ctx, "foo/bar", "foo/bar/baz/boq.txt")
+
+	expectedPath := filepath.Join(ctx.Config().BazelContext.OutputBase(), "execroot/__main__/foo/bar/baz/boq.txt")
+	if out.String() != expectedPath {
+		t.Errorf("incorrect OutputPath: expected %q, got %q", expectedPath, out.String())
+	}
+
+	expectedRelPath := "baz/boq.txt"
+	if out.Rel() != expectedRelPath {
+		t.Errorf("incorrect OutputPath.Rel(): expected %q, got %q", expectedRelPath, out.Rel())
+	}
+}
+
+func TestPathForBazelOutRelativeUnderBinFolder(t *testing.T) {
+	ctx := &TestBazelPathContext{}
+	out := PathForBazelOutRelative(ctx, "foo/bar", "bazel-out/linux_x86_64-fastbuild-ST-b4ef1c4402f9/bin/foo/bar/baz/boq.txt")
+
+	expectedPath := filepath.Join(ctx.Config().BazelContext.OutputBase(), "execroot/__main__/bazel-out/linux_x86_64-fastbuild-ST-b4ef1c4402f9/bin/foo/bar/baz/boq.txt")
+	if out.String() != expectedPath {
+		t.Errorf("incorrect OutputPath: expected %q, got %q", expectedPath, out.String())
+	}
+
+	expectedRelPath := "baz/boq.txt"
+	if out.Rel() != expectedRelPath {
+		t.Errorf("incorrect OutputPath.Rel(): expected %q, got %q", expectedRelPath, out.Rel())
+	}
+}
+
+func TestPathForBazelOutOutsideOfExecroot(t *testing.T) {
+	ctx := &TestBazelPathContext{}
+	out := PathForBazelOut(ctx, "../bazel_tools/linux_x86_64-fastbuild/bin/tools/android/java_base_extras.jar")
+
+	expectedPath := filepath.Join(ctx.Config().BazelContext.OutputBase(), "execroot/bazel_tools/linux_x86_64-fastbuild/bin/tools/android/java_base_extras.jar")
+	if out.String() != expectedPath {
+		t.Errorf("incorrect OutputPath: expected %q, got %q", expectedPath, out.String())
+	}
+
+	expectedRelPath := "execroot/bazel_tools/linux_x86_64-fastbuild/bin/tools/android/java_base_extras.jar"
+	if out.Rel() != expectedRelPath {
+		t.Errorf("incorrect OutputPath.Rel(): expected %q, got %q", expectedRelPath, out.Rel())
+	}
+}
+
+func TestPathForBazelOutRelativeWithParentDirectoryRoot(t *testing.T) {
+	ctx := &TestBazelPathContext{}
+	out := PathForBazelOutRelative(ctx, "../bazel_tools", "../bazel_tools/foo/bar/baz.sh")
+
+	expectedPath := filepath.Join(ctx.Config().BazelContext.OutputBase(), "execroot/bazel_tools/foo/bar/baz.sh")
+	if out.String() != expectedPath {
+		t.Errorf("incorrect OutputPath: expected %q, got %q", expectedPath, out.String())
+	}
+
+	expectedRelPath := "foo/bar/baz.sh"
+	if out.Rel() != expectedRelPath {
+		t.Errorf("incorrect OutputPath.Rel(): expected %q, got %q", expectedRelPath, out.Rel())
+	}
+}
diff --git a/android/filegroup.go b/android/filegroup.go
index 14ed783..9e5769a 100644
--- a/android/filegroup.go
+++ b/android/filegroup.go
@@ -178,8 +178,7 @@
 
 	bazelOuts := make(Paths, 0, len(filePaths))
 	for _, p := range filePaths {
-		src := PathForBazelOut(ctx, p)
-		bazelOuts = append(bazelOuts, src)
+		bazelOuts = append(bazelOuts, PathForBazelOutRelative(ctx, ctx.ModuleDir(), p))
 	}
 
 	fg.srcs = bazelOuts