The accurate solution of the incompressible Navier-Stokes equations requires high mesh resolution and very efficient algebraic solution strategies. The best overall efficiency can be obtained by using multigrid techniques which usually contain highly recursive components. This makes the effective parallelization of these methods difficult, as good parallel efficiency may strongly conflict with the goal of high numerical efficiency. We describe a multigrid-based Navier-Stokes solver which combines these two goals to a large extent. The algorithm uses operator splitting in the sense of the projection (or pressure correction) method where the inner linearized problems are solved by multigrid iterations. The parallel efficiency is achieved by grid-blocking in the smoothing process without reducing the overall numerical efficiency too much.