diff --git a/app/models/cells/deleted_claim.rb b/app/models/cells/deleted_claim.rb
new file mode 100644
index 0000000000000000000000000000000000000000..20b12ec0e7e3dda0702ff884b1f5fb68b5a4ba05
--- /dev/null
+++ b/app/models/cells/deleted_claim.rb
@@ -0,0 +1,13 @@
+# frozen_string_literal: true
+
+module Cells
+  class DeletedClaim < ApplicationRecord
+    scope :for_table, ->(table_name) { where(source_table: table_name) }
+    scope :recent, -> { order(created_at: :desc) }
+    scope :old, -> { where(created_at: ...1.hour.ago) }
+
+    def claim_key
+      [source_table, source_record_id]
+    end
+  end
+end
diff --git a/db/docs/cells_deleted_claims.yml b/db/docs/cells_deleted_claims.yml
new file mode 100644
index 0000000000000000000000000000000000000000..65a7f516f2159fe5573018b635a3400c2ea6e4aa
--- /dev/null
+++ b/db/docs/cells_deleted_claims.yml
@@ -0,0 +1,11 @@
+---
+table_name: cells_deleted_claims
+classes:
+- Cells::DeletedClaim
+feature_categories:
+- cell
+description: Cells Deleted claims related to lease releases.
+introduced_by_url: https://gitlab.com/gitlab-org/gitlab/-/merge_requests/204871
+milestone: '18.5'
+gitlab_schema: gitlab_main_cell_local
+table_size: small
diff --git a/db/migrate/20251006102914_create_cells_deleted_claims.rb b/db/migrate/20251006102914_create_cells_deleted_claims.rb
new file mode 100644
index 0000000000000000000000000000000000000000..d7c026865a776fda2dea1c807c245f5d33f96cbc
--- /dev/null
+++ b/db/migrate/20251006102914_create_cells_deleted_claims.rb
@@ -0,0 +1,63 @@
+# frozen_string_literal: true
+
+class CreateCellsDeletedClaims < Gitlab::Database::Migration[2.3]
+  milestone '18.5'
+  disable_ddl_transaction!
+
+  def up
+    create_table :cells_deleted_claims, if_not_exists: true do |t| # rubocop:disable Migration/EnsureFactoryForTable -- False positive
+      t.timestamps_with_timezone null: false
+      t.bigint :source_record_id, null: false
+      t.text :source_table, null: false, limit: 63
+
+      t.index [:source_record_id, :source_table], unique: true,
+        name: 'index_deleted_claims_on_source_record_id_and_source_table'
+    end
+
+    execute <<~SQL
+      CREATE OR REPLACE FUNCTION record_claim_deletion()
+      RETURNS TRIGGER AS $$
+      BEGIN
+        BEGIN
+          INSERT INTO cells_deleted_claims (
+            source_record_id,
+            source_table,
+            created_at,
+            updated_at
+          ) VALUES (
+            OLD.id,
+            TG_TABLE_NAME,
+            CURRENT_TIMESTAMP,
+            CURRENT_TIMESTAMP
+          );
+        EXCEPTION WHEN OTHERS THEN
+          NULL;
+        END;
+
+        RETURN OLD;
+      END;
+      $$ LANGUAGE plpgsql;
+    SQL
+
+    execute <<~SQL
+      CREATE OR REPLACE TRIGGER gpg_key_subkeys_deletion_audit
+      BEFORE DELETE ON gpg_key_subkeys
+      FOR EACH ROW
+      EXECUTE FUNCTION record_claim_deletion();
+    SQL
+
+    execute <<~SQL
+      CREATE OR REPLACE TRIGGER emails_deletion_audit
+      BEFORE DELETE ON emails
+      FOR EACH ROW
+      EXECUTE FUNCTION record_claim_deletion();
+    SQL
+  end
+
+  def down
+    execute "DROP TRIGGER IF EXISTS gpg_key_subkeys_deletion_audit ON gpg_key_subkeys;"
+    execute "DROP TRIGGER IF EXISTS emails_deletion_audit ON emails;"
+    execute "DROP FUNCTION IF EXISTS record_claim_deletion() CASCADE;"
+    drop_table :cells_deleted_claims
+  end
+end
diff --git a/db/schema_migrations/20251006102914 b/db/schema_migrations/20251006102914
new file mode 100644
index 0000000000000000000000000000000000000000..95928f19566164155126a1c27def88f0eaff19c1
--- /dev/null
+++ b/db/schema_migrations/20251006102914
@@ -0,0 +1 @@
+5eb9386d5131421877434c882b10eb11ab00704979e5031f4e31c5d887aefd40
\ No newline at end of file
diff --git a/db/structure.sql b/db/structure.sql
index 4a8ed4a43b55f386551434a7d989afd93460c453..929889da884d024086df860b33b938c1223abd56 100644
--- a/db/structure.sql
+++ b/db/structure.sql
@@ -773,6 +773,30 @@ RETURN OLD;
 END
 $$;
 
+CREATE FUNCTION record_claim_deletion() RETURNS trigger
+    LANGUAGE plpgsql
+    AS $$
+BEGIN
+  BEGIN
+    INSERT INTO cells_deleted_claims (
+      source_record_id,
+      source_table,
+      created_at,
+      updated_at
+    ) VALUES (
+      OLD.id,
+      TG_TABLE_NAME,
+      CURRENT_TIMESTAMP,
+      CURRENT_TIMESTAMP
+    );
+  EXCEPTION WHEN OTHERS THEN
+    NULL;
+  END;
+
+  RETURN OLD;
+END;
+$$;
+
 CREATE FUNCTION set_has_external_issue_tracker() RETURNS trigger
     LANGUAGE plpgsql
     AS $$
@@ -13330,6 +13354,24 @@ CREATE SEQUENCE catalog_verified_namespaces_id_seq
 
 ALTER SEQUENCE catalog_verified_namespaces_id_seq OWNED BY catalog_verified_namespaces.id;
 
+CREATE TABLE cells_deleted_claims (
+    id bigint NOT NULL,
+    created_at timestamp with time zone NOT NULL,
+    updated_at timestamp with time zone NOT NULL,
+    source_record_id bigint NOT NULL,
+    source_table text NOT NULL,
+    CONSTRAINT check_1d15f820fa CHECK ((char_length(source_table) <= 63))
+);
+
+CREATE SEQUENCE cells_deleted_claims_id_seq
+    START WITH 1
+    INCREMENT BY 1
+    NO MINVALUE
+    NO MAXVALUE
+    CACHE 1;
+
+ALTER SEQUENCE cells_deleted_claims_id_seq OWNED BY cells_deleted_claims.id;
+
 CREATE TABLE cells_outstanding_leases (
     uuid uuid NOT NULL,
     created_at timestamp with time zone NOT NULL,
@@ -30683,6 +30725,8 @@ ALTER TABLE ONLY catalog_resources ALTER COLUMN id SET DEFAULT nextval('catalog_
 
 ALTER TABLE ONLY catalog_verified_namespaces ALTER COLUMN id SET DEFAULT nextval('catalog_verified_namespaces_id_seq'::regclass);
 
+ALTER TABLE ONLY cells_deleted_claims ALTER COLUMN id SET DEFAULT nextval('cells_deleted_claims_id_seq'::regclass);
+
 ALTER TABLE ONLY chat_names ALTER COLUMN id SET DEFAULT nextval('chat_names_id_seq'::regclass);
 
 ALTER TABLE ONLY chat_teams ALTER COLUMN id SET DEFAULT nextval('chat_teams_id_seq'::regclass);
@@ -33236,6 +33280,9 @@ ALTER TABLE ONLY catalog_resources
 ALTER TABLE ONLY catalog_verified_namespaces
     ADD CONSTRAINT catalog_verified_namespaces_pkey PRIMARY KEY (id);
 
+ALTER TABLE ONLY cells_deleted_claims
+    ADD CONSTRAINT cells_deleted_claims_pkey PRIMARY KEY (id);
+
 ALTER TABLE ONLY cells_outstanding_leases
     ADD CONSTRAINT cells_outstanding_leases_pkey PRIMARY KEY (uuid);
 
@@ -39609,6 +39656,8 @@ CREATE INDEX index_dast_sites_on_dast_site_validation_id ON dast_sites USING btr
 
 CREATE UNIQUE INDEX index_dast_sites_on_project_id_and_url ON dast_sites USING btree (project_id, url);
 
+CREATE UNIQUE INDEX index_deleted_claims_on_source_record_id_and_source_table ON cells_deleted_claims USING btree (source_record_id, source_table);
+
 CREATE UNIQUE INDEX index_dep_prox_manifests_on_group_id_file_name_and_status ON dependency_proxy_manifests USING btree (group_id, file_name, status);
 
 CREATE INDEX index_dependency_list_export_parts_on_dependency_list_export_id ON dependency_list_export_parts USING btree (dependency_list_export_id);
@@ -46931,6 +46980,10 @@ CREATE TRIGGER clusters_loose_fk_trigger AFTER DELETE ON clusters REFERENCING OL
 
 CREATE TRIGGER duo_workflows_workflows_loose_fk_trigger AFTER DELETE ON duo_workflows_workflows REFERENCING OLD TABLE AS old_table FOR EACH STATEMENT EXECUTE FUNCTION insert_into_loose_foreign_keys_deleted_records();
 
+CREATE TRIGGER emails_deletion_audit BEFORE DELETE ON emails FOR EACH ROW EXECUTE FUNCTION record_claim_deletion();
+
+CREATE TRIGGER gpg_key_subkeys_deletion_audit BEFORE DELETE ON gpg_key_subkeys FOR EACH ROW EXECUTE FUNCTION record_claim_deletion();
+
 CREATE TRIGGER group_type_ci_runner_machines_loose_fk_trigger AFTER DELETE ON group_type_ci_runner_machines REFERENCING OLD TABLE AS old_table FOR EACH STATEMENT EXECUTE FUNCTION insert_into_loose_foreign_keys_deleted_records_override_table('ci_runner_machines');
 
 CREATE TRIGGER group_type_ci_runners_loose_fk_trigger AFTER DELETE ON group_type_ci_runners REFERENCING OLD TABLE AS old_table FOR EACH STATEMENT EXECUTE FUNCTION insert_into_loose_foreign_keys_deleted_records_override_table('ci_runners');
diff --git a/spec/db/schema_spec.rb b/spec/db/schema_spec.rb
index f944b8685281773be2d79cd698c291bd3b5d03a8..4f97e7001cdbcca9877a1ecebed74246b8e59da5 100644
--- a/spec/db/schema_spec.rb
+++ b/spec/db/schema_spec.rb
@@ -66,6 +66,7 @@
       boards: %w[milestone_id iteration_id],
       broadcast_messages: %w[namespace_id],
       catalog_resource_component_last_usages: %w[used_by_project_id], # No FK constraint because we want to preserve usage data even if project is deleted.
+      cells_deleted_claims: %w[source_record_id],
       chat_names: %w[chat_id team_id],
       chat_teams: %w[team_id],
       ci_build_needs: %w[project_id],
diff --git a/spec/factories/cells/deleted_claim.rb b/spec/factories/cells/deleted_claim.rb
new file mode 100644
index 0000000000000000000000000000000000000000..8ace176c4e676bf02811402c23d48c28f2940165
--- /dev/null
+++ b/spec/factories/cells/deleted_claim.rb
@@ -0,0 +1,8 @@
+# frozen_string_literal: true
+
+FactoryBot.define do
+  factory :cells_deleted_claim, class: 'Cells::DeletedClaim' do
+    source_record_id { rand(1..1000) }
+    source_table { %w[users gpg_key_subkeys].sample }
+  end
+end
diff --git a/spec/models/cells/deleted_claim_spec.rb b/spec/models/cells/deleted_claim_spec.rb
new file mode 100644
index 0000000000000000000000000000000000000000..ce74c4f516cb00f0363118b9dc497b9ee8fc9a5e
--- /dev/null
+++ b/spec/models/cells/deleted_claim_spec.rb
@@ -0,0 +1,53 @@
+# frozen_string_literal: true
+
+require 'spec_helper'
+
+RSpec.describe Cells::DeletedClaim, feature_category: :cell do
+  describe 'scopes' do
+    let_it_be(:email_claim) { described_class.create!(source_record_id: 123, source_table: 'emails') }
+    let_it_be(:gpg_claim) { described_class.create!(source_record_id: 456, source_table: 'gpg_key_subkeys') }
+    let_it_be(:old_claim) do
+      described_class.create!(source_record_id: 789, source_table: 'emails', created_at: 2.hours.ago)
+    end
+
+    describe '.for_table' do
+      it 'filters by source table' do
+        expect(described_class.for_table('emails')).to contain_exactly(email_claim, old_claim)
+        expect(described_class.for_table('gpg_key_subkeys')).to contain_exactly(gpg_claim)
+      end
+    end
+
+    describe '.recent' do
+      it 'orders by created_at descending' do
+        expect(described_class.recent).to eq([gpg_claim, email_claim, old_claim])
+      end
+    end
+
+    describe '.old' do
+      it 'returns claims older than 1 hour' do
+        expect(described_class.old).to contain_exactly(old_claim)
+      end
+    end
+  end
+
+  describe '#claim_key' do
+    let(:deleted_claim) { described_class.new(source_table: 'emails', source_record_id: 123) }
+
+    it 'returns array with source_table and source_record_id' do
+      expect(deleted_claim.claim_key).to eq(['emails', 123])
+    end
+  end
+
+  describe 'integration with trigger' do
+    it 'creates a deleted claim when an email is destroyed' do
+      email = create(:email)
+
+      expect { email.destroy! }.to change { described_class.count }.by(1)
+
+      deleted_claim = described_class.last
+
+      expect(deleted_claim.source_table).to eq('emails')
+      expect(deleted_claim.source_record_id).to eq(email.id)
+    end
+  end
+end
diff --git a/spec/models/email_spec.rb b/spec/models/email_spec.rb
index bdc4945bc729e0c2c24982863d1cc7a573135170..8c7a1153bfa6832cf50c4c0e94143c0c560b5738 100644
--- a/spec/models/email_spec.rb
+++ b/spec/models/email_spec.rb
@@ -244,4 +244,16 @@
       end
     end
   end
+
+  describe 'emails_deletion_audit trigger' do
+    before do
+      create_list(:email, 4, user: user)
+    end
+
+    it 'invokes the record_claim_deletion() trigger and creates the record in cells_deleted_claims' do
+      expect do
+        user.destroy!
+      end.to change { Cells::DeletedClaim.count }.by(5)
+    end
+  end
 end
diff --git a/spec/models/gpg_key_subkey_spec.rb b/spec/models/gpg_key_subkey_spec.rb
index c1d9e2bde43bd93ef5208864674b245659ab4d5d..a5aa52c96cbb05d4c69784c3bf3f8d4c4297ea29 100644
--- a/spec/models/gpg_key_subkey_spec.rb
+++ b/spec/models/gpg_key_subkey_spec.rb
@@ -14,4 +14,21 @@
     it { is_expected.to validate_presence_of(:fingerprint) }
     it { is_expected.to validate_presence_of(:keyid) }
   end
+
+  describe 'gpg_key_subkeys_deletion_audit trigger' do
+    let_it_be(:user) { create(:user) }
+
+    before do
+      create(:gpg_key, user: user)
+    end
+
+    it 'invokes the record_claim_deletion() trigger and creates the record in cells_deleted_claims' do
+      expect do
+        user.destroy!
+      end.to change { Cells::DeletedClaim.count }.by(2)
+
+      sources = Cells::DeletedClaim.limit(2).pluck(:source_table)
+      expect(sources).to match_array(%w[emails gpg_key_subkeys])
+    end
+  end
 end