Elevation map generation is an essential component of any autonomous underwater vehicle designed to navigate close to the seafloor because elevation maps are used for obstacle avoidance, path planning and self localization. We present an algorithm for the reconstruction of elevation maps of the seafloor from side-scan sonar backscatter images and sparse bathymetric points co-registered within the image. Given the trajectory for the underwater vehicle, the reconstruction is corrected for the attitude of the side-scan sonar during the image generation process. To perform reconstruction, an arbitrary but computable scattering model is assumed for the seafloor backscatter. The algorithm uses the sparse bathymetric data to generate an initial estimate for the elevation map which is then iteratively refined to fit the backscatter image by minimizing a global error functional. Concurrently, the parameters of the scattering model are determined on a coarse grid in the image by fitting the assumed scattering model to the backscatter data. The reconstruction is corrected for the movement of the sensor by initially doing local reconstructions in sensor coordinates and then transforming the local reconstructions to a global coordinate system using vehicle attitude and performing the reconstruction again. We demonstrate the effectiveness of our algorithm on synthetic and real data sets. Our algorithm is shown to decrease the average elevation error when compared to real bathymetry from 4.6 meters for the initial surface estimate to 1.6 meters for the final surface estimate from a survey taken of the Juan de Fuca Ridge.