diff --git a/app/finders/branches_finder.rb b/app/finders/branches_finder.rb
index 157c454183a6fbc48f851afd0c4f00789ba5e766..747f178a0eb4b97f350dc67e5c2865f4d25e01b4 100644
--- a/app/finders/branches_finder.rb
+++ b/app/finders/branches_finder.rb
@@ -26,7 +26,7 @@ def per_page
   end
 
   def page_token
-    "#{Gitlab::Git::BRANCH_REF_PREFIX}#{@params[:page_token]}" if @params[:page_token]
+    "#{Gitlab::Git::BRANCH_REF_PREFIX}#{@params[:page_token]}" if @params[:page_token] && Feature.enabled?(:branch_list_keyset_pagination, repository.project, default_enabled: :yaml)
   end
 
   def pagination_params
diff --git a/config/feature_flags/development/branch_api_first_page_performance.yml b/config/feature_flags/development/branch_api_first_page_performance.yml
new file mode 100644
index 0000000000000000000000000000000000000000..0a1e2553a6be226bdb49c35be0d096eecf62aba5
--- /dev/null
+++ b/config/feature_flags/development/branch_api_first_page_performance.yml
@@ -0,0 +1,8 @@
+---
+name: branch_api_first_page_performance
+introduced_by_url: https://gitlab.com/gitlab-org/gitlab/-/merge_requests/61692
+rollout_issue_url:
+milestone: '13.12'
+type: development
+group: group::source code
+default_enabled: false
diff --git a/lib/gitlab/pagination/gitaly_keyset_pager.rb b/lib/gitlab/pagination/gitaly_keyset_pager.rb
index b05891066acae450c83802096e333eed845f28db..0d4a0907d9faf3f485dbe4bef7509d37b96aff25 100644
--- a/lib/gitlab/pagination/gitaly_keyset_pager.rb
+++ b/lib/gitlab/pagination/gitaly_keyset_pager.rb
@@ -15,9 +15,14 @@ def initialize(request_context, project)
       # and supports pagination via gitaly.
       def paginate(finder)
         return paginate_via_gitaly(finder) if keyset_pagination_enabled?
-        return paginate_first_page_via_gitaly(finder) if paginate_first_page?
 
-        branches = ::Kaminari.paginate_array(finder.execute)
+        branches =
+          if paginate_first_page?
+            ::Kaminari.paginate_array(finder.execute(gitaly_pagination: true), total_count: project.repository.branch_count)
+          else
+            ::Kaminari.paginate_array(finder.execute)
+          end
+
         Gitlab::Pagination::OffsetPagination
           .new(request_context)
           .paginate(branches)
@@ -30,7 +35,10 @@ def keyset_pagination_enabled?
       end
 
       def paginate_first_page?
-        Feature.enabled?(:branch_list_keyset_pagination, project, default_enabled: :yaml) && (params[:page].blank? || params[:page].to_i == 1)
+        return false unless Feature.enabled?(:branch_api_first_page_performance, project, default_enabled: :yaml)
+        return false if params[:search].present? || params[:names].present?
+
+        params[:page].blank? || params[:page].to_i == 1
       end
 
       def paginate_via_gitaly(finder)
@@ -39,20 +47,6 @@ def paginate_via_gitaly(finder)
         end
       end
 
-      # When first page is requested, we paginate the data via Gitaly
-      # Headers are added to immitate offset pagination, while it is the default option
-      def paginate_first_page_via_gitaly(finder)
-        finder.execute(gitaly_pagination: true).tap do |records|
-          total = project.repository.branch_count
-          per_page = params[:per_page].presence || Kaminari.config.default_per_page
-
-          Gitlab::Pagination::OffsetHeaderBuilder.new(
-            request_context: request_context, per_page: per_page, page: 1, next_page: 2,
-            total: total, total_pages: total / per_page + 1
-          ).execute
-        end
-      end
-
       def apply_headers(records)
         if records.count == params[:per_page]
           Gitlab::Pagination::Keyset::HeaderBuilder
diff --git a/spec/finders/branches_finder_spec.rb b/spec/finders/branches_finder_spec.rb
index a62dd3842dbe9bda55929945b4ea88022500d334..f66bd2683fd46710e950ee03fb560c07d0b99961 100644
--- a/spec/finders/branches_finder_spec.rb
+++ b/spec/finders/branches_finder_spec.rb
@@ -185,6 +185,20 @@
         end
       end
 
+      context 'when branch_list_keyset_pagination is disabled' do
+        let(:params) { { page_token: 'feature', per_page: 2 } }
+
+        before do
+          stub_feature_flags(branch_list_keyset_pagination: false)
+        end
+
+        it 'page_token is not taken into account' do
+          result = subject
+
+          expect(result.map(&:name)).to eq(["'test'", '2-mb-file'])
+        end
+      end
+
       context 'by next page_token and per_page' do
         let(:params) { { page_token: 'fix', per_page: 2 } }
 
diff --git a/spec/lib/gitlab/pagination/gitaly_keyset_pager_spec.rb b/spec/lib/gitlab/pagination/gitaly_keyset_pager_spec.rb
index 132a0e9ca78ef97ea8ccb760fb4d60db534f9e89..71255f582c70f39a204b7308dbcf04dfd23a680a 100644
--- a/spec/lib/gitlab/pagination/gitaly_keyset_pager_spec.rb
+++ b/spec/lib/gitlab/pagination/gitaly_keyset_pager_spec.rb
@@ -11,9 +11,12 @@
   let(:finder) { double("branch finder") }
   let(:custom_port) { 8080 }
   let(:incoming_api_projects_url) { "#{Gitlab.config.gitlab.url}:#{custom_port}/api/v4/projects" }
+  let(:fake_request) { double(url: "#{incoming_api_projects_url}?#{query.to_query}") }
 
   before do
     stub_config_setting(port: custom_port)
+
+    allow(request_context).to receive(:request).and_return(fake_request)
   end
 
   describe '.paginate' do
@@ -40,9 +43,10 @@
       end
     end
 
-    context 'with branch_list_keyset_pagination feature off' do
+    context 'with branch_list_keyset_pagination and branch_api_first_page_performance feature off' do
       before do
         stub_feature_flags(branch_list_keyset_pagination: false)
+        stub_feature_flags(branch_api_first_page_performance: false)
       end
 
       context 'without keyset pagination option' do
@@ -57,7 +61,6 @@
     end
 
     context 'with branch_list_keyset_pagination feature on' do
-      let(:fake_request) { double(url: "#{incoming_api_projects_url}?#{query.to_query}") }
       let(:branch1) { double 'branch', name: 'branch1' }
       let(:branch2) { double 'branch', name: 'branch2' }
       let(:branch3) { double 'branch', name: 'branch3' }
@@ -66,39 +69,10 @@
         stub_feature_flags(branch_list_keyset_pagination: project)
       end
 
-      context 'without keyset pagination option' do
-        context 'when first page is requested' do
-          let(:branches) { [branch1, branch2, branch3] }
-
-          it 'keyset pagination is used with offset headers' do
-            allow(request_context).to receive(:request).and_return(fake_request)
-            allow(project.repository).to receive(:branch_count).and_return(branches.size)
-
-            expect(finder).to receive(:execute).with(gitaly_pagination: true).and_return(branches)
-            expect(request_context).to receive(:header).with('X-Per-Page', '2')
-            expect(request_context).to receive(:header).with('X-Page', '1')
-            expect(request_context).to receive(:header).with('X-Next-Page', '2')
-            expect(request_context).to receive(:header).with('X-Prev-Page', '')
-            expect(request_context).to receive(:header).with('Link', kind_of(String))
-            expect(request_context).to receive(:header).with('X-Total', '3')
-            expect(request_context).to receive(:header).with('X-Total-Pages', '2')
-
-            pager.paginate(finder)
-          end
-        end
-
-        context 'when second page is requested' do
-          let(:base_query) { { per_page: 2, page: 2 } }
-
-          it_behaves_like 'offset pagination'
-        end
-      end
-
       context 'with keyset pagination option' do
         let(:query) { base_query.merge(pagination: 'keyset') }
 
         before do
-          allow(request_context).to receive(:request).and_return(fake_request)
           expect(finder).to receive(:execute).with(gitaly_pagination: true).and_return(branches)
         end
 
@@ -127,5 +101,45 @@
         end
       end
     end
+
+    context 'when first page is requested' do
+      let(:branch1) { double 'branch', name: 'branch1' }
+      let(:branch2) { double 'branch', name: 'branch2' }
+      let(:branch3) { double 'branch', name: 'branch3' }
+      let(:branches) { [branch1, branch2, branch3] }
+
+      it 'keyset pagination is used with offset headers' do
+        allow(project.repository).to receive(:branch_count).and_return(branches.size)
+
+        expect(finder).to receive(:execute).with(gitaly_pagination: true).and_return(branches)
+        expect(request_context).to receive(:header).with('X-Per-Page', '2')
+        expect(request_context).to receive(:header).with('X-Page', '1')
+        expect(request_context).to receive(:header).with('X-Next-Page', '2')
+        expect(request_context).to receive(:header).with('X-Prev-Page', '')
+        expect(request_context).to receive(:header).with('Link', kind_of(String))
+        expect(request_context).to receive(:header).with('X-Total', '3')
+        expect(request_context).to receive(:header).with('X-Total-Pages', '2')
+
+        pager.paginate(finder)
+      end
+
+      context 'when second page is requested' do
+        let(:base_query) { { per_page: 2, page: 2 } }
+
+        it_behaves_like 'offset pagination'
+      end
+
+      context 'when names param is passed' do
+        let(:base_query) { { per_page: 2, page: 1, names: 'a' } }
+
+        it_behaves_like 'offset pagination'
+      end
+
+      context 'when search param is passed' do
+        let(:base_query) { { per_page: 2, page: 1, search: 'a' } }
+
+        it_behaves_like 'offset pagination'
+      end
+    end
   end
 end
diff --git a/spec/requests/api/branches_spec.rb b/spec/requests/api/branches_spec.rb
index d697ad85d95cea7ee5c3f17a6f9d09af880c9ce7..033e1eba38741bec31ff92b5f9776ef6f0ad6065 100644
--- a/spec/requests/api/branches_spec.rb
+++ b/spec/requests/api/branches_spec.rb
@@ -20,7 +20,7 @@
     stub_feature_flags(branch_list_keyset_pagination: false)
   end
 
-  describe "GET /projects/:id/repository/branches" do
+  describe "GET /projects/:id/repository/branches", :use_clean_rails_redis_caching do
     let(:route) { "/projects/#{project_id}/repository/branches" }
 
     shared_examples_for 'repository branches' do
@@ -161,12 +161,17 @@ def check_merge_status(json_response)
     context 'when search parameter is passed' do
       context 'and branch exists' do
         it 'returns correct branches' do
-          get api(route, user), params: { per_page: 100, search: branch_name }
+          get api(route, user), params: { per_page: 5, search: branch_name }
 
           searched_branch_names = json_response.map { |branch| branch['name'] }
-          project_branch_names = project.repository.branch_names.grep(/#{branch_name}/)
+          expect(searched_branch_names).to eq(%w(feature feature_conflict))
+        end
+
+        it 'returns paginated results' do
+          get api(route, user), params: { per_page: 1, search: branch_name }
 
-          expect(searched_branch_names).to match_array(project_branch_names)
+          searched_branch_names = json_response.map { |branch| branch['name'] }
+          expect(searched_branch_names).to eq(%w(feature))
         end
       end