diff --git a/tests/bp2build_bazel_test.sh b/tests/bp2build_bazel_test.sh
index 090114b..88ab682 100755
--- a/tests/bp2build_bazel_test.sh
+++ b/tests/bp2build_bazel_test.sh
@@ -330,6 +330,12 @@
   if [[ -L "./out/soong/workspace/foo/F2D" ]] || [[ ! -d "./out/soong/workspace/foo/F2D" ]]; then
     fail "./out/soong/workspace/foo/F2D should be a dir"
   fi
+
+  # relative symlinks
+  local BAZEL_BIN_RELATIVE_SYMLINK=`readlink out/soong/workspace/build/bazel/bin`
+  if [[ $BAZEL_BIN_RELATIVE_SYMLINK != "../../../../../build/bazel/bin" ]]; then
+    fail "out/soong/workspace/build/bazel/bin should be a relative symlink"
+  fi
 }
 
 function test_cc_correctness {
diff --git a/tests/lib.sh b/tests/lib.sh
index 0766d85..d934470 100644
--- a/tests/lib.sh
+++ b/tests/lib.sh
@@ -8,10 +8,15 @@
 
 REAL_TOP="$(readlink -f "$(dirname "$0")"/../../..)"
 
+function make_mock_top {
+  mock=$(mktemp -t -d st.XXXXX)
+  echo "$mock"
+}
+
 if [[ -n "$HARDWIRED_MOCK_TOP" ]]; then
   MOCK_TOP="$HARDWIRED_MOCK_TOP"
 else
-  MOCK_TOP=$(mktemp -t -d st.XXXXX)
+  MOCK_TOP=$(make_mock_top)
   trap cleanup_mock_top EXIT
 fi
 
@@ -197,3 +202,10 @@
     info "Completed test case \e[96;1m$f\e[0m"
   done
 }
+
+function move_mock_top {
+  MOCK_TOP2=$(make_mock_top)
+  mv $MOCK_TOP $MOCK_TOP2
+  MOCK_TOP=$MOCK_TOP2
+  trap cleanup_mock_top EXIT
+}
diff --git a/tests/relative_symlinks_test.sh b/tests/relative_symlinks_test.sh
new file mode 100755
index 0000000..9477f8c
--- /dev/null
+++ b/tests/relative_symlinks_test.sh
@@ -0,0 +1,90 @@
+#!/bin/bash -eu
+
+set -o pipefail
+
+# Test that relative symlinks work by recreating the bug in b/259191764
+# In some cases, developers prefer to move their checkouts. This causes
+# issues in that symlinked files (namely, the bazel wrapper script)
+# cannot be found. As such, we implemented relative symlinks so that a
+# moved checkout doesn't need a full clean before rebuilding.
+# The bazel output base will still need to be removed, as Starlark
+# doesn't seem to support relative symlinks yet.
+
+source "$(dirname "$0")/lib.sh"
+
+function test_movable_top_bazel_build {
+  setup
+
+  mkdir -p a
+  touch a/g.txt
+  cat > a/Android.bp <<'EOF'
+filegroup {
+    name: "g",
+    srcs: ["g.txt"],
+    bazel_module: {bp2build_available: true},
+}
+EOF
+  # A directory under $MOCK_TOP
+  outdir=out2
+
+  # Modify OUT_DIR in a subshell so it doesn't affect the top level one.
+  (export OUT_DIR=$MOCK_TOP/$outdir; run_soong bp2build && run_bazel build --config=bp2build --config=ci //a:g)
+
+  move_mock_top
+
+  # remove the bazel output base
+  rm -rf $outdir/bazel/output_user_root
+  (export OUT_DIR=$MOCK_TOP/$outdir; run_soong bp2build && run_bazel build --config=bp2build --config=ci //a:g)
+}
+
+function test_movable_top_soong_build {
+  setup
+
+  mkdir -p a
+  touch a/g.txt
+  cat > a/Android.bp <<'EOF'
+filegroup {
+    name: "g",
+    srcs: ["g.txt"],
+}
+EOF
+
+  # A directory under $MOCK_TOP
+  outdir=out2
+
+  # Modify OUT_DIR in a subshell so it doesn't affect the top level one.
+  (export OUT_DIR=$MOCK_TOP/$outdir; run_soong g)
+
+  move_mock_top
+
+  # remove the bazel output base
+  rm -rf $outdir/bazel/output
+  (export OUT_DIR=$MOCK_TOP/$outdir; run_soong g)
+}
+
+function test_remove_output_base_and_ninja_file {
+  # If the bazel output base is removed without the ninja file, the build will fail
+  # This tests that removing both the bazel output base and ninja file will succeed
+  # without a clean
+  setup
+
+  mkdir -p a
+  touch a/g.txt
+  cat > a/Android.bp <<'EOF'
+filegroup {
+    name: "g",
+    srcs: ["g.txt"],
+}
+EOF
+  outdir=out2
+
+  # Modify OUT_DIR in a subshell so it doesn't affect the top level one.
+  (export OUT_DIR=$MOCK_TOP/$outdir; run_soong g)
+  # remove the bazel output base
+  rm -rf $outdir/bazel/output
+  rm $outdir/soong/build*ninja
+
+  (export OUT_DIR=$MOCK_TOP/$outdir; run_soong g)
+}
+
+scan_and_run_tests
diff --git a/tests/run_integration_tests.sh b/tests/run_integration_tests.sh
index 6b9ff8b..5789f52 100755
--- a/tests/run_integration_tests.sh
+++ b/tests/run_integration_tests.sh
@@ -23,4 +23,5 @@
 "$TOP/build/soong/tests/apex_cc_module_arch_variant_tests.sh" "aosp_cf_arm64_phone" "armv8-a" "cortex-a53"
 
 "$TOP/build/bazel/ci/b_test.sh"
+"$TOP/build/soong/tests/relative_symlinks_test.sh"