A fast computational method for fully nonlinear non-overturning water waves is derived in two and three dimensions. A corresponding time-stepping scheme is developed in the two-dimensional case. The essential part of the method is a fast converging iterative solution procedure of the Laplace equation. One part of the solution is obtained by fast Fourier transform, while another part is highly nonlinear and consists of integrals with kernels that decay quickly in space. The number of operations required is asymptotically O(N log N), where N is the number of nodes at the free surface. While any accuracy of the computations is achieved by a continued iteration of the equations, one iteration is found to be sufficient for practical computations, while maintaining high accuracy. The resulting explicit approximation of the scheme is tested in two versions. Simulations of nonlinear wave fields with wave slope even up to about unity compare very well with reference computations. The numerical scheme is formulated in such a way that aliasing terms are partially or completely avoided.