diff --git a/ee/changelogs/unreleased/parallel-push-check.yml b/ee/changelogs/unreleased/parallel-push-check.yml
new file mode 100644
index 0000000000000000000000000000000000000000..4b1de04e77a36173e3cb7b1f12e60c05cad87538
--- /dev/null
+++ b/ee/changelogs/unreleased/parallel-push-check.yml
@@ -0,0 +1,5 @@
+---
+title: Run PushRuleCheck in parallel
+merge_request: 45668
+author:
+type: performance
diff --git a/ee/config/feature_flags/ops/parallel_push_checks.yml b/ee/config/feature_flags/ops/parallel_push_checks.yml
new file mode 100644
index 0000000000000000000000000000000000000000..958cadc3241708ad9fb1d735e5268451cb35a99a
--- /dev/null
+++ b/ee/config/feature_flags/ops/parallel_push_checks.yml
@@ -0,0 +1,7 @@
+---
+name: parallel_push_checks
+introduced_by_url: https://gitlab.com/gitlab-org/gitlab/-/merge_requests/45668
+rollout_issue_url: 
+type: ops
+group: group::source_code
+default_enabled: false
diff --git a/ee/lib/ee/gitlab/checks/push_rule_check.rb b/ee/lib/ee/gitlab/checks/push_rule_check.rb
index 34edd6a9122d32078e56b0f5b4c0ee8d4b9fb102..441aeafa4a1012785398af02f1a6b1c8d13644a6 100644
--- a/ee/lib/ee/gitlab/checks/push_rule_check.rb
+++ b/ee/lib/ee/gitlab/checks/push_rule_check.rb
@@ -7,14 +7,86 @@ class PushRuleCheck < ::Gitlab::Checks::BaseChecker
         def validate!
           return unless push_rule
 
+          if ::Feature.enabled?(:parallel_push_checks, project, type: :ops)
+            run_checks_in_parallel!
+          else
+            run_checks_in_sequence!
+          end
+        end
+
+        private
+
+        # @return [Nil] returns nil unless an error is raised
+        # @raise [Gitlab::GitAccess::ForbiddenError] if check fails
+        def check_tag_or_branch!
           if tag_name
             PushRules::TagCheck.new(change_access).validate!
           else
             PushRules::BranchCheck.new(change_access).validate!
           end
+        end
 
+        # @return [Nil] returns nil unless an error is raised
+        # @raise [Gitlab::GitAccess::ForbiddenError] if check fails
+        def check_file_size!
           PushRules::FileSizeCheck.new(change_access).validate!
         end
+
+        # Run the checks one after the other.
+        #
+        # @return [Nil] returns nil unless an error is raised
+        # @raise [Gitlab::GitAccess::ForbiddenError] if any check fails
+        def run_checks_in_sequence!
+          check_tag_or_branch!
+          check_file_size!
+        end
+
+        # Run the checks in separate threads for performance benefits
+        #
+        # @return [Nil] returns nil unless an error is raised
+        # @raise [Gitlab::GitAccess::ForbiddenError] if any check fails
+        def run_checks_in_parallel!
+          @threads = []
+
+          parallelize do
+            check_tag_or_branch!
+          end
+
+          parallelize do
+            check_file_size!
+          end
+
+          # Block whilst waiting for threads, however if one errors
+          # it will exit early and raise the error immediately as
+          # we set `abort_on_exception` to true.
+          @threads.each(&:join)
+
+          nil
+        ensure
+          # We want to make sure no threads are left dangling.
+          # Threads can exit early when an exception is raised
+          # and so we want to ensure any still running are exited
+          # as soon as possible.
+          @threads.each(&:exit)
+        end
+
+        # Runs a block inside a new thread. This thread will
+        # exit immediately upon an exception being raised.
+        #
+        # @raise [Gitlab::GitAccess::ForbiddenError]
+        def parallelize
+          @threads << Thread.new do
+            Thread.current.tap do |t|
+              t.name = "push_rule_check"
+              t.abort_on_exception = true
+              t.report_on_exception = false
+            end
+
+            yield
+          ensure # rubocop: disable Layout/RescueEnsureAlignment
+            ActiveRecord::Base.clear_active_connections!
+          end
+        end
       end
     end
   end
diff --git a/ee/spec/lib/ee/gitlab/checks/push_rule_check_spec.rb b/ee/spec/lib/ee/gitlab/checks/push_rule_check_spec.rb
index 1efdca234b24b9b5650b69a040945bd072e9c066..bb860b111a9e1decc4b3b94e7514df2f4cd4bbdc 100644
--- a/ee/spec/lib/ee/gitlab/checks/push_rule_check_spec.rb
+++ b/ee/spec/lib/ee/gitlab/checks/push_rule_check_spec.rb
@@ -7,10 +7,24 @@
 
   let(:push_rule) { create(:push_rule, :commit_message) }
 
-  describe '#validate!' do
+  shared_examples "push checks" do
     before do
-      expect_any_instance_of(EE::Gitlab::Checks::PushRules::FileSizeCheck)
-        .to receive(:validate!)
+      allow_any_instance_of(EE::Gitlab::Checks::PushRules::FileSizeCheck)
+        .to receive(:validate!).and_return(nil)
+      allow_any_instance_of(EE::Gitlab::Checks::PushRules::TagCheck)
+        .to receive(:validate!).and_return(nil)
+      allow_any_instance_of(EE::Gitlab::Checks::PushRules::BranchCheck)
+        .to receive(:validate!).and_return(nil)
+    end
+
+    it "returns nil on success" do
+      expect(subject.validate!).to be_nil
+    end
+
+    it "raises an error on failure" do
+      expect_any_instance_of(EE::Gitlab::Checks::PushRules::FileSizeCheck).to receive(:validate!).and_raise(Gitlab::GitAccess::ForbiddenError)
+
+      expect { subject.validate! }.to raise_error(Gitlab::GitAccess::ForbiddenError)
     end
 
     context 'when tag name exists' do
@@ -43,4 +57,16 @@
       end
     end
   end
+
+  describe '#validate!' do
+    it_behaves_like "push checks"
+
+    context ":parallel_push_checks feature is disabled" do
+      before do
+        stub_feature_flags(parallel_push_checks: false)
+      end
+
+      it_behaves_like "push checks"
+    end
+  end
 end