diff --git a/app/models/ci/build.rb b/app/models/ci/build.rb
index 34b5b637422fb48f15997524820e0d230be42486..7f42b21bc8722f52493d786499efd6428a2e0264 100644
--- a/app/models/ci/build.rb
+++ b/app/models/ci/build.rb
@@ -1135,6 +1135,17 @@ def test_suite_name
       end
     end
 
+    def partition_id_token_prefix
+      partition_id.to_s(16) if Feature.enabled?(:ci_build_partition_id_token_prefix, project)
+    end
+
+    override :format_token
+    def format_token(token)
+      return token if partition_id_token_prefix.nil?
+
+      "#{partition_id_token_prefix}_#{token}"
+    end
+
     protected
 
     def run_status_commit_hooks!
diff --git a/config/feature_flags/development/ci_build_partition_id_token_prefix.yml b/config/feature_flags/development/ci_build_partition_id_token_prefix.yml
new file mode 100644
index 0000000000000000000000000000000000000000..5b3cd22a489bbde3296c0c452e6263253a844ca8
--- /dev/null
+++ b/config/feature_flags/development/ci_build_partition_id_token_prefix.yml
@@ -0,0 +1,8 @@
+---
+name: ci_build_partition_id_token_prefix
+introduced_by_url: https://gitlab.com/gitlab-org/gitlab/-/merge_requests/106179
+rollout_issue_url: https://gitlab.com/gitlab-org/gitlab/-/issues/385401
+milestone: '15.7'
+type: development
+group: group::pipeline execution
+default_enabled: false
diff --git a/spec/models/ci/build_spec.rb b/spec/models/ci/build_spec.rb
index 5f1937d078c12bd26ecfb895a037cb42be937783..5fbfe9b3bd6fc9e5b3857ad7faffc9c52d49dec6 100644
--- a/spec/models/ci/build_spec.rb
+++ b/spec/models/ci/build_spec.rb
@@ -5643,4 +5643,33 @@ def run_job_without_exception
       expect(ci_build.job_variables.second.partition_id).to eq(ci_testing_partition_id)
     end
   end
+
+  describe 'assigning token', :ci_partitionable do
+    include Ci::PartitioningHelpers
+
+    let(:new_pipeline) { create(:ci_pipeline) }
+    let(:ci_build) { create(:ci_build, pipeline: new_pipeline) }
+
+    before do
+      stub_current_partition_id
+    end
+
+    it 'includes partition_id as a token prefix' do
+      prefix = ci_build.token.split('_').first.to_i(16)
+
+      expect(prefix).to eq(ci_testing_partition_id)
+    end
+
+    context 'when ci_build_partition_id_token_prefix is disabled' do
+      before do
+        stub_feature_flags(ci_build_partition_id_token_prefix: false)
+      end
+
+      it 'does not include partition_id as a token prefix' do
+        prefix = ci_build.token.split('_').first.to_i(16)
+
+        expect(prefix).not_to eq(ci_testing_partition_id)
+      end
+    end
+  end
 end