This work is concerned with a nonlinear Galerkin method for solving the incompressible Navier-Stokes equation on the sphere. It extends the work of Debussche, Marion,Shen, Temam et al. from one-dimensional or toroidal domains to the spherical geometry. In the first part, the method based on type 3 vector spherical harmonics is introduced and convergence is indicated. Further it is shown that the occurring coupling terms involving three vector spherical harmonics can be expressed algebraically in terms of Wigner-3j coefficients. To improve the numerical efficiency and economy we introduce an FFT based pseudo spectral algorithm for computing the Fourier coefficients of the nonlinear advection term. The resulting method scales with O(N^3), if N denotes the maximal spherical harmonic degree. The latter is demonstrated in an extensive numerical example.