A new Volterra integral equation of the second kind with square integrable kernel is derived for paraxial propagation of radiowaves over a gently varying, perfectly conducting rough surface. The integral equation is solved exactly in terms of a infinite series and the necessary and sufficient conditions for the solution to exist and converge are established. Super exponential convergence of the Neumann series for arbitrary surface slope is established through asymptotic analysis. Expressions are derived for the determination of the number of terms needed to achieve a given accuracy, the latter depending on the parameters of the rough surface, the frequency of operation and the maximum range. Numerical results with truncated series are compared with that obtained by solving the integral equation numerically for a sinusoidal surface, Gaussian hill, and a random rough surface with Pierson-Moskowitz spectrum.