diff --git a/db/docs/batched_background_migrations/backfill_workspace_personal_access_token.yml b/db/docs/batched_background_migrations/backfill_workspace_personal_access_token.yml
new file mode 100644
index 0000000000000000000000000000000000000000..53433fbb1c7856d207e05a4ea036ed5682b5bc01
--- /dev/null
+++ b/db/docs/batched_background_migrations/backfill_workspace_personal_access_token.yml
@@ -0,0 +1,5 @@
+migration_job_name: BackfillWorkspacePersonalAccessToken
+description: Create personal access token for workspaces without one
+feature_category: remote_development
+introduced_by_url: https://gitlab.com/gitlab-org/gitlab/-/merge_requests/131516
+milestone: 16.4
diff --git a/db/post_migrate/20230909120000_queue_backfill_workspace_personal_access_token.rb b/db/post_migrate/20230909120000_queue_backfill_workspace_personal_access_token.rb
new file mode 100644
index 0000000000000000000000000000000000000000..5a746d9749358aa00c26be938de2e50d660c7493
--- /dev/null
+++ b/db/post_migrate/20230909120000_queue_backfill_workspace_personal_access_token.rb
@@ -0,0 +1,26 @@
+# frozen_string_literal: true
+
+class QueueBackfillWorkspacePersonalAccessToken < Gitlab::Database::Migration[2.1]
+  MIGRATION = "BackfillWorkspacePersonalAccessToken"
+  DELAY_INTERVAL = 2.minutes
+  BATCH_SIZE = 100
+  SUB_BATCH_SIZE = 10
+
+  restrict_gitlab_migration gitlab_schema: :gitlab_main
+  disable_ddl_transaction!
+
+  def up
+    queue_batched_background_migration(
+      MIGRATION,
+      :workspaces,
+      :id,
+      job_interval: DELAY_INTERVAL,
+      batch_size: BATCH_SIZE,
+      sub_batch_size: SUB_BATCH_SIZE
+    )
+  end
+
+  def down
+    delete_batched_background_migration(MIGRATION, :workspaces, :id, [])
+  end
+end
diff --git a/db/schema_migrations/20230909120000 b/db/schema_migrations/20230909120000
new file mode 100644
index 0000000000000000000000000000000000000000..414065b369367d5fa61e60401da933ad24bdcb36
--- /dev/null
+++ b/db/schema_migrations/20230909120000
@@ -0,0 +1 @@
+75402594bdc333a34f7b49db4d5008fddad10f346dd15d65e4552cac20b442fb
\ No newline at end of file
diff --git a/ee/lib/ee/gitlab/background_migration/backfill_workspace_personal_access_token.rb b/ee/lib/ee/gitlab/background_migration/backfill_workspace_personal_access_token.rb
new file mode 100644
index 0000000000000000000000000000000000000000..0d1687e8507ecfb1ca45b8bc9742f50f8ad6895e
--- /dev/null
+++ b/ee/lib/ee/gitlab/background_migration/backfill_workspace_personal_access_token.rb
@@ -0,0 +1,55 @@
+# frozen_string_literal: true
+
+module EE
+  module Gitlab
+    module BackgroundMigration
+      # This class is responsible for backfilling personal access tokens for workspaces without one.
+      module BackfillWorkspacePersonalAccessToken
+        extend ActiveSupport::Concern
+        extend ::Gitlab::Utils::Override
+
+        prepended do
+          operation_name :backfill
+          scope_to ->(relation) {
+            relation.where(personal_access_token_id: nil)
+          }
+          feature_category :remote_development
+        end
+
+        class PersonalAccessToken < ::ApplicationRecord
+          self.table_name = 'personal_access_tokens'
+        end
+
+        override :perform
+        def perform
+          each_sub_batch do |sub_batch|
+            sub_batch.each do |workspace|
+              expires_at = calculate_expires_at(workspace.created_at, workspace.max_hours_before_termination)
+              revoked = calculate_revoked(expires_at, workspace.desired_state)
+              ApplicationRecord.transaction do
+                pat = PersonalAccessToken.create!(
+                  name: workspace.name,
+                  user_id: workspace.user_id,
+                  impersonation: false,
+                  scopes: [:write_repository],
+                  expires_at: expires_at,
+                  revoked: revoked
+                )
+
+                workspace.update! personal_access_token_id: pat.id
+              end
+            end
+          end
+        end
+
+        def calculate_expires_at(created_at, max_hours_before_termination)
+          (created_at + max_hours_before_termination.hour).to_date.next_day
+        end
+
+        def calculate_revoked(expires_at, desired_state)
+          expires_at <= Date.today || desired_state == ::RemoteDevelopment::Workspaces::States::TERMINATED
+        end
+      end
+    end
+  end
+end
diff --git a/ee/spec/lib/gitlab/background_migration/backfill_workspace_personal_access_token_spec.rb b/ee/spec/lib/gitlab/background_migration/backfill_workspace_personal_access_token_spec.rb
new file mode 100644
index 0000000000000000000000000000000000000000..7b0c1c2eb1b6764138f73dabdd7ef0846e6ba28a
--- /dev/null
+++ b/ee/spec/lib/gitlab/background_migration/backfill_workspace_personal_access_token_spec.rb
@@ -0,0 +1,140 @@
+# frozen_string_literal: true
+
+require 'spec_helper'
+
+RSpec.describe Gitlab::BackgroundMigration::BackfillWorkspacePersonalAccessToken, feature_category: :remote_development do
+  describe "#perform" do
+    let(:workspace_attrs) do
+      {
+        user_id: user.id,
+        project_id: project.id,
+        cluster_agent_id: cluster_agent.id,
+        desired_state_updated_at: 2.seconds.ago,
+        max_hours_before_termination: 19,
+        namespace: 'ns',
+        actual_state: ::RemoteDevelopment::Workspaces::States::RUNNING,
+        desired_state: ::RemoteDevelopment::Workspaces::States::RUNNING,
+        editor: 'e',
+        devfile_ref: 'dfr',
+        devfile_path: 'dev/path',
+        config_version: 1,
+        url: 'https://www.example.org'
+      }
+    end
+
+    let(:namespace) { table(:namespaces).create!(name: 'namespace', path: 'namespace') }
+    let(:project) do
+      table(:projects).create!(name: 'project', path: 'project', project_namespace_id: namespace.id,
+        namespace_id: namespace.id)
+    end
+
+    let(:cluster_agent) { table(:cluster_agents).create!(name: 'cluster_agent', project_id: project.id) }
+    let(:user) { table(:users).create!(email: 'author@example.com', username: 'author', projects_limit: 10) }
+    let(:workspaces_table) { table(:workspaces) }
+    let(:personal_access_tokens_table) { table(:personal_access_tokens) }
+    let!(:pat) do
+      personal_access_tokens_table.create!(name: 'workspace1', user_id: user.id, scopes: "---\n- api\n",
+        expires_at: 4.days.from_now)
+    end
+
+    let!(:workspace_without_personal_access_token) do
+      workspaces_table.create!({
+        name: 'workspace1',
+        personal_access_token_id: nil
+      }.merge!(workspace_attrs))
+    end
+
+    let!(:workspace_with_personal_access_token) do
+      workspaces_table.create!({
+        name: 'workspace2',
+        personal_access_token_id: pat.id
+      }.merge!(workspace_attrs))
+    end
+
+    let(:migration) do
+      described_class.new(
+        start_id: workspace_without_personal_access_token.id,
+        end_id: workspace_with_personal_access_token.id,
+        batch_table: :workspaces,
+        batch_column: :id,
+        sub_batch_size: 2,
+        pause_ms: 0,
+        connection: ApplicationRecord.connection
+      )
+    end
+
+    it "creates a personal access token and updates the workspace" do
+      expect { migration.perform }.to change {
+                                        workspace_without_personal_access_token.reload.personal_access_token_id
+                                      }.from(nil)
+    end
+
+    it "does not modify workspace's existing token" do
+      expect { migration.perform }.not_to change {
+                                            workspace_with_personal_access_token.reload.personal_access_token_id
+                                          }
+    end
+  end
+
+  describe "#calculate_expires_at" do
+    let(:migration) do
+      described_class.new(
+        start_id: 1,
+        end_id: 2,
+        batch_table: :workspaces,
+        batch_column: :id,
+        sub_batch_size: 2,
+        pause_ms: 0,
+        connection: ApplicationRecord.connection
+      )
+    end
+
+    it "calculates the expiration date correctly" do
+      created_at = DateTime.parse("2023-09-13 12:00:00")
+      max_hours_before_termination = 24
+
+      expected_expires_at = DateTime.parse("2023-09-15")
+
+      result = migration.calculate_expires_at(created_at, max_hours_before_termination)
+      expect(result).to eq(expected_expires_at)
+    end
+  end
+
+  describe "#calculate_revoked" do
+    let(:migration) do
+      described_class.new(
+        start_id: 1,
+        end_id: 2,
+        batch_table: :workspaces,
+        batch_column: :id,
+        sub_batch_size: 2,
+        pause_ms: 0,
+        connection: ApplicationRecord.connection
+      )
+    end
+
+    it "returns true if expires_at is in the past" do
+      expires_at = DateTime.yesterday
+      desired_state = ::RemoteDevelopment::Workspaces::States::RUNNING
+
+      result = migration.calculate_revoked(expires_at, desired_state)
+      expect(result).to be(true)
+    end
+
+    it "returns true if desired_state is 'Terminated'" do
+      expires_at = DateTime.tomorrow
+      desired_state = ::RemoteDevelopment::Workspaces::States::TERMINATED
+
+      result = migration.calculate_revoked(expires_at, desired_state)
+      expect(result).to be(true)
+    end
+
+    it "returns false if expires_at is in the future and desired_state is not 'Terminated'" do
+      expires_at = DateTime.tomorrow
+      desired_state = ::RemoteDevelopment::Workspaces::States::RUNNING
+
+      result = migration.calculate_revoked(expires_at, desired_state)
+      expect(result).to be(false)
+    end
+  end
+end
diff --git a/ee/spec/migrations/20230909120000_queue_backfill_workspace_personal_access_token_spec.rb b/ee/spec/migrations/20230909120000_queue_backfill_workspace_personal_access_token_spec.rb
new file mode 100644
index 0000000000000000000000000000000000000000..a4a866294f4a8653b3e2dd33716938e68b81b1b6
--- /dev/null
+++ b/ee/spec/migrations/20230909120000_queue_backfill_workspace_personal_access_token_spec.rb
@@ -0,0 +1,26 @@
+# frozen_string_literal: true
+
+require 'spec_helper'
+require_migration!
+
+RSpec.describe QueueBackfillWorkspacePersonalAccessToken, feature_category: :remote_development do
+  let!(:batched_migration) { described_class::MIGRATION }
+
+  it 'schedules a new batched migration' do
+    reversible_migration do |migration|
+      migration.before -> {
+        expect(batched_migration).not_to have_scheduled_batched_migration
+      }
+
+      migration.after -> {
+        expect(batched_migration).to have_scheduled_batched_migration(
+          table_name: :workspaces,
+          column_name: :id,
+          interval: described_class::DELAY_INTERVAL.to_i,
+          batch_size: described_class::BATCH_SIZE,
+          sub_batch_size: described_class::SUB_BATCH_SIZE
+        )
+      }
+    end
+  end
+end
diff --git a/lib/gitlab/background_migration/backfill_workspace_personal_access_token.rb b/lib/gitlab/background_migration/backfill_workspace_personal_access_token.rb
new file mode 100644
index 0000000000000000000000000000000000000000..f71759dc8ddbfbed66c5081faf829ee88bf29bf1
--- /dev/null
+++ b/lib/gitlab/background_migration/backfill_workspace_personal_access_token.rb
@@ -0,0 +1,13 @@
+# frozen_string_literal: true
+
+module Gitlab
+  module BackgroundMigration
+    # No op on ce
+    class BackfillWorkspacePersonalAccessToken < BatchedMigrationJob
+      feature_category :remote_development
+      def perform; end
+    end
+  end
+end
+
+Gitlab::BackgroundMigration::BackfillWorkspacePersonalAccessToken.prepend_mod_with('Gitlab::BackgroundMigration::BackfillWorkspacePersonalAccessToken') # rubocop:disable Layout/LineLength