diff --git a/app/models/namespace.rb b/app/models/namespace.rb
index 7c6fa24cd4d5af0ba7a81752fdd32f0fae3985e9..52a6cbdafad8dc8a313ceed2b848dfc2f419e600 100644
--- a/app/models/namespace.rb
+++ b/app/models/namespace.rb
@@ -57,6 +57,7 @@ class Namespace < ApplicationRecord
   # This should _not_ be `inverse_of: :namespace`, because that would also set
   # `user.namespace` when this user creates a group with themselves as `owner`.
   belongs_to :owner, class_name: 'User'
+  belongs_to :organization
 
   belongs_to :parent, class_name: "Namespace"
   has_many :children, -> { where(type: Group.sti_name) }, class_name: "Namespace", foreign_key: :parent_id
diff --git a/app/models/organization.rb b/app/models/organization.rb
index cfbbbf1183ef57e94d0f55f7fe21ebf1cb93f753..0d03d95b5ffc04ea4631fbf293ca7b79a18e92b6 100644
--- a/app/models/organization.rb
+++ b/app/models/organization.rb
@@ -7,6 +7,9 @@ class Organization < ApplicationRecord
 
   before_destroy :check_if_default_organization
 
+  has_many :namespaces
+  has_many :groups
+
   validates :name,
     presence: true,
     length: { maximum: 255 },
diff --git a/config/gitlab_loose_foreign_keys.yml b/config/gitlab_loose_foreign_keys.yml
index 1f97975a8063a634ba98a96d526a9f98a61c05be..dfc4861d1f7f923f4d0f0b0d81cca053df831983 100644
--- a/config/gitlab_loose_foreign_keys.yml
+++ b/config/gitlab_loose_foreign_keys.yml
@@ -247,6 +247,10 @@ ml_candidates:
   - table: ci_builds
     column: ci_build_id
     on_delete: async_nullify
+namespaces:
+  - table: organizations
+    column: organization_id
+    on_delete: async_nullify
 p_ci_builds_metadata:
   - table: projects
     column: project_id
diff --git a/db/migrate/20230516044606_add_organization_id_to_namespace.rb b/db/migrate/20230516044606_add_organization_id_to_namespace.rb
new file mode 100644
index 0000000000000000000000000000000000000000..5569c0edb68fe1fe88249c8305f28acc9e86c004
--- /dev/null
+++ b/db/migrate/20230516044606_add_organization_id_to_namespace.rb
@@ -0,0 +1,11 @@
+# frozen_string_literal: true
+
+class AddOrganizationIdToNamespace < Gitlab::Database::Migration[2.1]
+  DEFAULT_ORGANIZATION_ID = 1
+
+  enable_lock_retries!
+
+  def change
+    add_column :namespaces, :organization_id, :bigint, default: DEFAULT_ORGANIZATION_ID, null: true # rubocop:disable Migration/AddColumnsToWideTables
+  end
+end
diff --git a/db/migrate/20230516045238_track_organization_record_changes.rb b/db/migrate/20230516045238_track_organization_record_changes.rb
new file mode 100644
index 0000000000000000000000000000000000000000..006074218672b6e179942fda7fabfd3c52174425
--- /dev/null
+++ b/db/migrate/20230516045238_track_organization_record_changes.rb
@@ -0,0 +1,15 @@
+# frozen_string_literal: true
+
+class TrackOrganizationRecordChanges < Gitlab::Database::Migration[2.1]
+  include Gitlab::Database::MigrationHelpers::LooseForeignKeyHelpers
+
+  enable_lock_retries!
+
+  def up
+    track_record_deletions(:organizations)
+  end
+
+  def down
+    untrack_record_deletions(:organizations)
+  end
+end
diff --git a/db/migrate/20230516045442_prepare_index_for_org_id_on_namespaces.rb b/db/migrate/20230516045442_prepare_index_for_org_id_on_namespaces.rb
new file mode 100644
index 0000000000000000000000000000000000000000..57283050eeba192e9c4d995f354596a9a51ff8ec
--- /dev/null
+++ b/db/migrate/20230516045442_prepare_index_for_org_id_on_namespaces.rb
@@ -0,0 +1,13 @@
+# frozen_string_literal: true
+
+class PrepareIndexForOrgIdOnNamespaces < Gitlab::Database::Migration[2.1]
+  INDEX_NAME = 'index_namespaces_on_organization_id'
+
+  def up
+    prepare_async_index :namespaces, :organization_id, name: INDEX_NAME
+  end
+
+  def down
+    unprepare_async_index :namespaces, :organization_id, name: INDEX_NAME
+  end
+end
diff --git a/db/schema_migrations/20230516044606 b/db/schema_migrations/20230516044606
new file mode 100644
index 0000000000000000000000000000000000000000..b8ff16b9baa360752b782fdd974467ff961bea46
--- /dev/null
+++ b/db/schema_migrations/20230516044606
@@ -0,0 +1 @@
+2cfada37b139bfc64aab871250f947275fb78cbf6df1a6fd71e4dd424db66e26
\ No newline at end of file
diff --git a/db/schema_migrations/20230516045238 b/db/schema_migrations/20230516045238
new file mode 100644
index 0000000000000000000000000000000000000000..7784967128c6f37385fa4432a4eac3a2ebdb3b26
--- /dev/null
+++ b/db/schema_migrations/20230516045238
@@ -0,0 +1 @@
+05ea1ebd6dd6547a074b63b8783a9c1088e42d849d787dc1babe1d4f9c950765
\ No newline at end of file
diff --git a/db/schema_migrations/20230516045442 b/db/schema_migrations/20230516045442
new file mode 100644
index 0000000000000000000000000000000000000000..968cdc168892344ec7817677d370d8cdda92c41a
--- /dev/null
+++ b/db/schema_migrations/20230516045442
@@ -0,0 +1 @@
+0449ecd4e28fdc64e73326e6b6d48ecdf9bfa26e3de37dc948ce86ee104c96e0
\ No newline at end of file
diff --git a/db/structure.sql b/db/structure.sql
index 8dea1331b6e926480ddd913ad23e71bbde1eff2d..14c4d6f271ad4f0c17d803556468636c0e78a9d0 100644
--- a/db/structure.sql
+++ b/db/structure.sql
@@ -18761,7 +18761,8 @@ CREATE TABLE namespaces (
     push_rule_id bigint,
     shared_runners_enabled boolean DEFAULT true NOT NULL,
     allow_descendants_override_disabled_shared_runners boolean DEFAULT false NOT NULL,
-    traversal_ids integer[] DEFAULT '{}'::integer[] NOT NULL
+    traversal_ids integer[] DEFAULT '{}'::integer[] NOT NULL,
+    organization_id bigint DEFAULT 1
 );
 
 CREATE SEQUENCE namespaces_id_seq
@@ -34523,6 +34524,8 @@ CREATE TRIGGER namespaces_loose_fk_trigger AFTER DELETE ON namespaces REFERENCIN
 
 CREATE TRIGGER nullify_merge_request_metrics_build_data_on_update BEFORE UPDATE ON merge_request_metrics FOR EACH ROW EXECUTE FUNCTION nullify_merge_request_metrics_build_data();
 
+CREATE TRIGGER organizations_loose_fk_trigger AFTER DELETE ON organizations REFERENCING OLD TABLE AS old_table FOR EACH STATEMENT EXECUTE FUNCTION insert_into_loose_foreign_keys_deleted_records();
+
 CREATE TRIGGER projects_loose_fk_trigger AFTER DELETE ON projects REFERENCING OLD TABLE AS old_table FOR EACH STATEMENT EXECUTE FUNCTION insert_into_loose_foreign_keys_deleted_records();
 
 CREATE TRIGGER push_rules_loose_fk_trigger AFTER DELETE ON push_rules REFERENCING OLD TABLE AS old_table FOR EACH STATEMENT EXECUTE FUNCTION insert_into_loose_foreign_keys_deleted_records();
diff --git a/spec/db/schema_spec.rb b/spec/db/schema_spec.rb
index 9f228c751279d552edd736f7d752a1721a3fc796..686654bda30315d4ac7f4177eda75f5a085a14e2 100644
--- a/spec/db/schema_spec.rb
+++ b/spec/db/schema_spec.rb
@@ -13,7 +13,8 @@
     # `search_index_id index_type` is the composite foreign key configured for `search_namespace_index_assignments`,
     # but in Search::NamespaceIndexAssignment model, only `search_index_id` is used as foreign key and indexed
     search_namespace_index_assignments: [%w[search_index_id index_type]],
-    slack_integrations_scopes: [%w[slack_api_scope_id]]
+    slack_integrations_scopes: [%w[slack_api_scope_id]],
+    namespaces: %w[organization_id] # this index is added in an async manner, hence it needs to be ignored in the first phase.
   }.with_indifferent_access.freeze
 
   TABLE_PARTITIONS = %w[ci_builds_metadata].freeze
diff --git a/spec/models/namespace_spec.rb b/spec/models/namespace_spec.rb
index 3ff49938de5791e29998942eb3a129fbe31e5e92..9cd05c8234a603ae8434e58c0367766f6cb891f1 100644
--- a/spec/models/namespace_spec.rb
+++ b/spec/models/namespace_spec.rb
@@ -15,6 +15,7 @@
   let(:repository_storage) { 'default' }
 
   describe 'associations' do
+    it { is_expected.to belong_to :organization }
     it { is_expected.to have_many :projects }
     it { is_expected.to have_many :project_statistics }
     it { is_expected.to belong_to :parent }
@@ -2687,4 +2688,11 @@ def expect_project_directories_at(namespace_path, with_pages: true)
       end
     end
   end
+
+  context 'with loose foreign key on organization_id' do
+    it_behaves_like 'cleanup by a loose foreign key' do
+      let!(:parent) { create(:organization) }
+      let!(:model) { create(:namespace, organization: parent) }
+    end
+  end
 end
diff --git a/spec/models/organization_spec.rb b/spec/models/organization_spec.rb
index e1aac88e6408cab8e5acde182374a7f6a6fcf203..5a73174bb7f4b7edd18a5caa61d247ad677ba16b 100644
--- a/spec/models/organization_spec.rb
+++ b/spec/models/organization_spec.rb
@@ -6,6 +6,11 @@
   let_it_be(:organization) { create(:organization) }
   let_it_be(:default_organization) { create(:organization, :default) }
 
+  describe 'associations' do
+    it { is_expected.to have_many :namespaces }
+    it { is_expected.to have_many :groups }
+  end
+
   describe 'validations' do
     subject { create(:organization) }