A multi-dimensional cell-vertex upwind discretization technique for the Navier-Strokes equations on unstructured grids is presented. The grids are composed of linear triangles in two and linear tetrahedra in three space dimensions. The nonlinear upwind schemes for the inviscid part can be viewed as a multi-dimensional generalization of the Roe-scheme, but also as a special class of Petrov-Galerkin schemes. They share with these schemes a compact Galerkin stencil, and are in addition monotonic by construction. The Petrov-Galerkin interpretation of the discretization technique allows a straightforward extension to the Navier-Strokes equations. For linear elements this boils down to a Galerkin discretization for the viscous terms. Compared to standard finite-volume methods on these grids, the method shows an increased accuracy, which becomes comparable with structured grid algorithms. The spatially discretized set of equations is integrated in time using the Backward Euler time integration method. The full Jacobian matrix is computed, either numerically by finite differences or approximated analytically, and stored. The resulting set of linear equations is solved by a Block MILU(0) preconditioned Krylov subspace method. For this purpose the Aztec library of SANDIA National Laboratories is used, which also takes care of the parallelization process and completely hides the details for the user. Results are presented for a two-dimensional turbulent shock wave boundary layer interaction in a nozzle and the turbulent flow over an ogive cylinder. All computations have been performed on the Cray T3E of the Technical University of Delft.