We investigate the utility of towed underwater camera systems with tightly coupled Global Navigation Satellite System (GNSS) positions to provide reef-scale bathymetric models with millimeter to centimeter resolutions and accuracies with Structure-from-Motion (SfM) photogrammetry. Successful development of these techniques would allow for detailed assessments of benthic conditions, including the accretion and erosion of reefs and adjacent sediment deposits, without the need for ground control points. We use a multi-camera system towed by a small vessel to map over 70,000 m² of complex shallow (2–8 m water depth) bedrock reef, boulder fields, and fine (sand and gravel) sediments of Lake Tahoe, California. We find that multiple synchronized cameras increase overall mapping coverage and allow for wider survey line spacing. The accuracy of the techniques was sub-millimeter for local length measurements less than a meter, and the bathymetric reproducibility was found to scale with the accuracy of GNSS (3–5 cm), although this could be improved to sub-centimeter with the inclusion of one or more co-registered, but unsurveyed, control points. For future applications, we provide guidance on conducting field operations, correcting underwater image color, and optimizing the SfM workflows. We conclude that a GNSS-coupled underwater camera array is a promising technique to map shallow reefs at high accuracy and resolution without ground control.