diff --git a/bp2build/symlink_forest.go b/bp2build/symlink_forest.go
index 5c33308..a0c7e4c 100644
--- a/bp2build/symlink_forest.go
+++ b/bp2build/symlink_forest.go
@@ -190,10 +190,20 @@
 
 // Creates a symbolic link at dst pointing to src
 func symlinkIntoForest(topdir, dst, src string) uint64 {
-	srcPath := shared.JoinPath(topdir, src)
-	dstPath := shared.JoinPath(topdir, dst)
+	// b/259191764 - Make all symlinks relative
+	dst = shared.JoinPath(topdir, dst)
+	src = shared.JoinPath(topdir, src)
+	basePath := filepath.Dir(dst)
+	var dstPath string
+	srcPath, err := filepath.Rel(basePath, src)
+	if err != nil {
+		fmt.Fprintf(os.Stderr, "Failed to find relative path for symlinking: %s\n", err)
+		os.Exit(1)
+	} else {
+		dstPath = dst
+	}
 
-	// Check if a symlink already exists.
+	// Check whether a symlink already exists.
 	if dstInfo, err := os.Lstat(dstPath); err != nil {
 		if !os.IsNotExist(err) {
 			fmt.Fprintf(os.Stderr, "Failed to lstat '%s': %s", dst, err)
diff --git a/scripts/prepare-moved-top.sh b/scripts/prepare-moved-top.sh
new file mode 100755
index 0000000..d941529
--- /dev/null
+++ b/scripts/prepare-moved-top.sh
@@ -0,0 +1,41 @@
+#!/bin/bash -eu
+
+###############
+# Removes the Bazel output base and ninja file.
+# This is intended to solve an issue when a build top is moved.
+# Starlark symlinks are absolute and a moved build top will have many
+# dangling symlinks and fail to function as intended.
+# If the bazel output base is removed WITHOUT the top moving,
+# then any subsequent builds will fail as soong_build will not rerun.
+# Removing the ninja file will force a re-execution.
+#
+# You MUST lunch again after moving your build top, before running this.
+###############
+
+if [[ ! -v ANDROID_BUILD_TOP ]]; then
+    echo "ANDROID_BUILD_TOP not found in environment. Please run lunch before running this script"
+    exit 1
+fi
+
+if [[ ! -v OUT_DIR ]]; then
+    out_dir="$ANDROID_BUILD_TOP/out"
+else
+    out_dir="$ANDROID_BUILD_TOP/$OUT_DIR"
+fi
+
+output_base=$out_dir/bazel/output/
+ninja_file=$out_dir/soong/build*ninja
+
+if [[ ! -d $output_base ]]; then
+    echo "The specified output directory doesn't exist."
+    echo "Have you rerun lunch since moving directories?"
+    exit 1
+fi
+
+read -p "Are you sure you want to remove $output_base and the ninja file $ninja_file? Y/N " -n 1 -r
+echo
+if [[ $REPLY =~ ^[Yy]$ ]]
+then
+   rm -rf $output_base
+   rm $ninja_file
+fi
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"