We present a novel finite element method for the Stokes problem on fictitious domains. We prove inf-sup stability, optimal order convergence and uniform boundedness of the condition number of the discrete system. The finite element formulation is based on a stabilized Nitsche method with ghost penalties for the velocity and pressure to obtain stability in the presence of small cut elements. We demonstrate for the first time the applicability of the Nitsche fictitious domain method to three-dimensional Stokes problems. We further discuss a general, flexible and freely available implementation of the method and present numerical examples supporting the theoretical results