diff --git a/GITALY_SERVER_VERSION b/GITALY_SERVER_VERSION
index 46448c71b9dffc30da18ba87beccc8440ef823a0..cb6b534abe1bbec8e58b5111f50894779e73405e 100644
--- a/GITALY_SERVER_VERSION
+++ b/GITALY_SERVER_VERSION
@@ -1 +1 @@
-0.57.0
+0.59.0
diff --git a/lib/gitlab/git/repository.rb b/lib/gitlab/git/repository.rb
index 129c077729aa44c5f3e887d776ab8c7819f3afc9..5625b695796dee1deee85eb1114699665669f4d3 100644
--- a/lib/gitlab/git/repository.rb
+++ b/lib/gitlab/git/repository.rb
@@ -1177,9 +1177,15 @@ def commit_index(user, branch_name, index, options)
       end
 
       def fsck
-        output, status = run_git(%W[--git-dir=#{path} fsck], nice: true)
+        gitaly_migrate(:git_fsck) do |is_enabled|
+          msg, status = if is_enabled
+                          gitaly_fsck
+                        else
+                          shell_fsck
+                        end
 
-        raise GitError.new("Could not fsck repository:\n#{output}") unless status.zero?
+          raise GitError.new("Could not fsck repository: #{msg}") unless status.zero?
+        end
       end
 
       def rebase(user, rebase_id, branch:, branch_sha:, remote_repository:, remote_branch:)
@@ -1327,6 +1333,14 @@ def configure_sparse_checkout(worktree_git_path, files)
         File.write(File.join(worktree_info_path, 'sparse-checkout'), files)
       end
 
+      def gitaly_fsck
+        gitaly_repository_client.fsck
+      end
+
+      def shell_fsck
+        run_git(%W[--git-dir=#{path} fsck], nice: true)
+      end
+
       def rugged_fetch_source_branch(source_repository, source_branch, local_ref)
         with_repo_branch_commit(source_repository, source_branch) do |commit|
           if commit
diff --git a/lib/gitlab/gitaly_client/repository_service.rb b/lib/gitlab/gitaly_client/repository_service.rb
index b9e606592d7e6274eef97475d1e88837dad5d37f..a477d618f63aadb6ad5ed1d34f105f20e3b8a077 100644
--- a/lib/gitlab/gitaly_client/repository_service.rb
+++ b/lib/gitlab/gitaly_client/repository_service.rb
@@ -87,6 +87,17 @@ def fetch_source_branch(source_repository, source_branch, local_ref)
 
         response.result
       end
+
+      def fsck
+        request = Gitaly::FsckRequest.new(repository: @gitaly_repo)
+        response = GitalyClient.call(@storage, :repository_service, :fsck, request)
+
+        if response.error.empty?
+          return "", 0
+        else
+          return response.error.b, 1
+        end
+      end
     end
   end
 end