diff --git a/app/models/appearance.rb b/app/models/appearance.rb
index fb66dd0b7668cce2143943356953563407fa9bb8..f8713138a93ae98913dbab2b26a2eabc54c83506 100644
--- a/app/models/appearance.rb
+++ b/app/models/appearance.rb
@@ -2,6 +2,7 @@ class Appearance < ActiveRecord::Base
   include CacheMarkdownField
   include AfterCommitQueue
   include ObjectStorage::BackgroundMove
+  include WithUploads
 
   cache_markdown_field :description
   cache_markdown_field :new_project_guidelines
@@ -14,8 +15,6 @@ class Appearance < ActiveRecord::Base
   mount_uploader :logo,         AttachmentUploader
   mount_uploader :header_logo,  AttachmentUploader
 
-  has_many :uploads, as: :model, dependent: :destroy # rubocop:disable Cop/ActiveRecordDependent
-
   CACHE_KEY = "current_appearance:#{Gitlab::VERSION}".freeze
 
   after_commit :flush_redis_cache
diff --git a/app/models/concerns/with_uploads.rb b/app/models/concerns/with_uploads.rb
new file mode 100644
index 0000000000000000000000000000000000000000..e7cfffb775b688b22ca546142c1425a085f99c6e
--- /dev/null
+++ b/app/models/concerns/with_uploads.rb
@@ -0,0 +1,39 @@
+# Mounted uploaders are destroyed by carrierwave's after_commit
+# hook. This hook fetches upload location (local vs remote) from
+# Upload model. So it's neccessary to make sure that during that
+# after_commit hook model's associated uploads are not deleted yet.
+# IOW we can not use dependent: :destroy :
+# has_many :uploads, as: :model, dependent: :destroy
+#
+# And because not-mounted uploads require presence of upload's
+# object model when destroying them (FileUploader's `build_upload` method
+# references `model` on delete), we can not use after_commit hook for these
+# uploads.
+#
+# Instead FileUploads are destroyed in before_destroy hook and remaining uploads
+# are destroyed by the carrierwave's after_commit hook.
+
+module WithUploads
+  extend ActiveSupport::Concern
+
+  # Currently there is no simple way how to select only not-mounted
+  # uploads, it should be all FileUploaders so we select them by
+  # `uploader` class
+  FILE_UPLOADERS = %w(PersonalFileUploader NamespaceFileUploader FileUploader).freeze
+
+  included do
+    has_many :uploads, as: :model
+
+    before_destroy :destroy_file_uploads
+  end
+
+  # mounted uploads are deleted in carrierwave's after_commit hook,
+  # but FileUploaders which are not mounted must be deleted explicitly and
+  # it can not be done in after_commit because FileUploader requires loads
+  # associated model on destroy (which is already deleted in after_commit)
+  def destroy_file_uploads
+    self.uploads.where(uploader: FILE_UPLOADERS).find_each do |upload|
+      upload.destroy
+    end
+  end
+end
diff --git a/app/models/group.rb b/app/models/group.rb
index cefca316399ffb26b77b0d011aebfb1c63d19c2d..8fb77a7869dda45deafebfeb8058d103ef58f7a3 100644
--- a/app/models/group.rb
+++ b/app/models/group.rb
@@ -10,6 +10,7 @@ class Group < Namespace
   include LoadedInGroupList
   include GroupDescendant
   include TokenAuthenticatable
+  include WithUploads
 
   has_many :group_members, -> { where(requested_at: nil) }, dependent: :destroy, as: :source # rubocop:disable Cop/ActiveRecordDependent
   alias_method :members, :group_members
@@ -30,8 +31,6 @@ class Group < Namespace
   has_many :variables, class_name: 'Ci::GroupVariable'
   has_many :custom_attributes, class_name: 'GroupCustomAttribute'
 
-  has_many :uploads, as: :model, dependent: :destroy # rubocop:disable Cop/ActiveRecordDependent
-
   has_many :boards
   has_many :badges, class_name: 'GroupBadge'
 
diff --git a/app/models/project.rb b/app/models/project.rb
index 534a0e630aff7f108b5a8181296895373fc3373e..0975e64e995a0acd36abecc04055dc612c01d580 100644
--- a/app/models/project.rb
+++ b/app/models/project.rb
@@ -23,6 +23,7 @@ class Project < ActiveRecord::Base
   include ::Gitlab::Utils::StrongMemoize
   include ChronicDurationAttribute
   include FastDestroyAll::Helpers
+  include WithUploads
 
   extend Gitlab::ConfigHelper
 
@@ -301,8 +302,6 @@ class Project < ActiveRecord::Base
     inclusion: { in: ->(_object) { Gitlab.config.repositories.storages.keys } }
   validates :variables, variable_duplicates: { scope: :environment_scope }
 
-  has_many :uploads, as: :model, dependent: :destroy # rubocop:disable Cop/ActiveRecordDependent
-
   # Scopes
   scope :pending_delete, -> { where(pending_delete: true) }
   scope :without_deleted, -> { where(pending_delete: false) }
diff --git a/app/models/user.rb b/app/models/user.rb
index 173ab38e20c71070cb57502ad873cc118c60896d..b90f5471071712212f2e192dca03083bc6ed3c73 100644
--- a/app/models/user.rb
+++ b/app/models/user.rb
@@ -17,6 +17,7 @@ class User < ActiveRecord::Base
   include IgnorableColumn
   include BulkMemberAccessLoad
   include BlocksJsonSerialization
+  include WithUploads
 
   DEFAULT_NOTIFICATION_LEVEL = :participating
 
@@ -137,7 +138,6 @@ def update_tracked_fields!(request)
 
   has_many :custom_attributes, class_name: 'UserCustomAttribute'
   has_many :callouts, class_name: 'UserCallout'
-  has_many :uploads, as: :model, dependent: :destroy # rubocop:disable Cop/ActiveRecordDependent
   has_many :term_agreements
   belongs_to :accepted_term, class_name: 'ApplicationSetting::Term'
 
diff --git a/changelogs/unreleased/jprovazn-remote-upload-destroy.yml b/changelogs/unreleased/jprovazn-remote-upload-destroy.yml
new file mode 100644
index 0000000000000000000000000000000000000000..22e55920fa3845bd681e7483aa27f60d62b603af
--- /dev/null
+++ b/changelogs/unreleased/jprovazn-remote-upload-destroy.yml
@@ -0,0 +1,5 @@
+---
+title: Fix deletion of Object Store uploads
+merge_request:
+author:
+type: fixed
diff --git a/lib/api/groups.rb b/lib/api/groups.rb
index 92e3d5cc10a4fcf2199d4101b396801389846f9f..0d125cd783170001d3e2a376fcfe7c9665311181 100644
--- a/lib/api/groups.rb
+++ b/lib/api/groups.rb
@@ -165,6 +165,7 @@ def present_groups(params, groups)
         group = find_group!(params[:id])
         authorize! :admin_group, group
 
+        Gitlab::QueryLimiting.whitelist('https://gitlab.com/gitlab-org/gitlab-ce/issues/46285')
         destroy_conditionally!(group) do |group|
           ::Groups::DestroyService.new(group, current_user).execute
         end
diff --git a/lib/api/v3/groups.rb b/lib/api/v3/groups.rb
index 2c52d21fa1c1af724bfa933d75b97bbafd574499..3844fd4810d0b695f618cc21c41df8c2508af6f8 100644
--- a/lib/api/v3/groups.rb
+++ b/lib/api/v3/groups.rb
@@ -131,6 +131,7 @@ def present_groups(groups, options = {})
         delete ":id" do
           group = find_group!(params[:id])
           authorize! :admin_group, group
+          Gitlab::QueryLimiting.whitelist('https://gitlab.com/gitlab-org/gitlab-ce/issues/46285')
           present ::Groups::DestroyService.new(group, current_user).execute, with: Entities::GroupDetail, current_user: current_user
         end
 
diff --git a/spec/models/appearance_spec.rb b/spec/models/appearance_spec.rb
index 56b5d6162846c627f2b238e544b8002da0216c4d..5489c17bd82e9857526870a6204589165ac9d280 100644
--- a/spec/models/appearance_spec.rb
+++ b/spec/models/appearance_spec.rb
@@ -5,7 +5,7 @@
 
   it { is_expected.to be_valid }
 
-  it { is_expected.to have_many(:uploads).dependent(:destroy) }
+  it { is_expected.to have_many(:uploads) }
 
   describe '.current', :use_clean_rails_memory_store_caching do
     let!(:appearance) { create(:appearance) }
@@ -41,4 +41,12 @@
       expect(new_row.valid?).to eq(false)
     end
   end
+
+  context 'with uploads' do
+    it_behaves_like 'model with mounted uploader', false do
+      let(:model_object) { create(:appearance, :with_logo) }
+      let(:upload_attribute) { :logo }
+      let(:uploader_class) { AttachmentUploader }
+    end
+  end
 end
diff --git a/spec/models/group_spec.rb b/spec/models/group_spec.rb
index 0907d28d33bb3fcdbd1dc6f5660dea19e7d15abf..f83b52e8975d127c84ede3244061acdc1c35a578 100644
--- a/spec/models/group_spec.rb
+++ b/spec/models/group_spec.rb
@@ -15,7 +15,7 @@
     it { is_expected.to have_many(:notification_settings).dependent(:destroy) }
     it { is_expected.to have_many(:labels).class_name('GroupLabel') }
     it { is_expected.to have_many(:variables).class_name('Ci::GroupVariable') }
-    it { is_expected.to have_many(:uploads).dependent(:destroy) }
+    it { is_expected.to have_many(:uploads) }
     it { is_expected.to have_one(:chat_team) }
     it { is_expected.to have_many(:custom_attributes).class_name('GroupCustomAttribute') }
     it { is_expected.to have_many(:badges).class_name('GroupBadge') }
@@ -691,4 +691,12 @@ def setup_group_members(group)
       end
     end
   end
+
+  context 'with uploads' do
+    it_behaves_like 'model with mounted uploader', true do
+      let(:model_object) { create(:group, :with_avatar) }
+      let(:upload_attribute) { :avatar }
+      let(:uploader_class) { AttachmentUploader }
+    end
+  end
 end
diff --git a/spec/models/project_spec.rb b/spec/models/project_spec.rb
index 5b452f179797e972311f7ce8a068b7993110b862..39625b559ebafd51c2865e8657f4904ef1d10224 100644
--- a/spec/models/project_spec.rb
+++ b/spec/models/project_spec.rb
@@ -76,7 +76,7 @@
     it { is_expected.to have_many(:project_group_links) }
     it { is_expected.to have_many(:notification_settings).dependent(:delete_all) }
     it { is_expected.to have_many(:forks).through(:forked_project_links) }
-    it { is_expected.to have_many(:uploads).dependent(:destroy) }
+    it { is_expected.to have_many(:uploads) }
     it { is_expected.to have_many(:pipeline_schedules) }
     it { is_expected.to have_many(:members_and_requesters) }
     it { is_expected.to have_many(:clusters) }
@@ -3739,4 +3739,12 @@ def domain_variable
       it { is_expected.to be_nil }
     end
   end
+
+  context 'with uploads' do
+    it_behaves_like 'model with mounted uploader', true do
+      let(:model_object) { create(:project, :with_avatar) }
+      let(:upload_attribute) { :avatar }
+      let(:uploader_class) { AttachmentUploader }
+    end
+  end
 end
diff --git a/spec/models/user_spec.rb b/spec/models/user_spec.rb
index bb5308221f0e520578defaddeac7dec20237840a..9dff6173f9475e2e61f5f107d79df4d08c76ce6c 100644
--- a/spec/models/user_spec.rb
+++ b/spec/models/user_spec.rb
@@ -39,7 +39,7 @@
     it { is_expected.to have_many(:builds).dependent(:nullify) }
     it { is_expected.to have_many(:pipelines).dependent(:nullify) }
     it { is_expected.to have_many(:chat_names).dependent(:destroy) }
-    it { is_expected.to have_many(:uploads).dependent(:destroy) }
+    it { is_expected.to have_many(:uploads) }
     it { is_expected.to have_many(:reported_abuse_reports).dependent(:destroy).class_name('AbuseReport') }
     it { is_expected.to have_many(:custom_attributes).class_name('UserCustomAttribute') }
 
@@ -2769,4 +2769,12 @@ def access_levels(groups)
       expect { user.increment_failed_attempts! }.not_to change(user, :failed_attempts)
     end
   end
+
+  context 'with uploads' do
+    it_behaves_like 'model with mounted uploader', false do
+      let(:model_object) { create(:user, :with_avatar) }
+      let(:upload_attribute) { :avatar }
+      let(:uploader_class) { AttachmentUploader }
+    end
+  end
 end
diff --git a/spec/support/shared_examples/models/with_uploads_shared_examples.rb b/spec/support/shared_examples/models/with_uploads_shared_examples.rb
new file mode 100644
index 0000000000000000000000000000000000000000..47ad0c6345d181f28553b8f6b9f70d37fa9d6298
--- /dev/null
+++ b/spec/support/shared_examples/models/with_uploads_shared_examples.rb
@@ -0,0 +1,23 @@
+require 'spec_helper'
+
+shared_examples_for 'model with mounted uploader' do |supports_fileuploads|
+  describe '.destroy' do
+    before do
+      stub_uploads_object_storage(uploader_class)
+
+      model_object.public_send(upload_attribute).migrate!(ObjectStorage::Store::REMOTE)
+    end
+
+    it 'deletes remote uploads' do
+      expect_any_instance_of(CarrierWave::Storage::Fog::File).to receive(:delete).and_call_original
+
+      expect { model_object.destroy }.to change { Upload.count }.by(-1)
+    end
+
+    it 'deletes any FileUploader uploads which are not mounted', skip: !supports_fileuploads do
+      create(:upload, uploader: FileUploader, model: model_object)
+
+      expect { model_object.destroy }.to change { Upload.count }.by(-2)
+    end
+  end
+end