Stochastic groundwater models enable the characterization of geological uncertainty. Often the major source of uncertainty is not related to aquifer heterogeneity, but to the general shape of the aquifer. This is especially the case in paleovalley-type alluvial aquifers where the bedrock surface limits the extent of easily extractable groundwater. Determining the shape of a bedrock surface is not straightforward, because it is typically non-stationary and defined by few data points that are generally far apart. This paper presents a new workflow for the stochastic reconstruction of bedrock surfaces using limited datasets that are typically available for aquifer characterization. The method is based on a lateral propagation of basement cross-sections interpreted from geophysical surveys, and conditions the reconstructed surface to existing well-log data and digital elevation model. To alleviate the typical limitations of sparse data, we use an analog approach to incorporate prior geological knowledge. We test the methodology on a synthetic example and a dataset from an alluvial aquifer in Northern Chile. Results of these case studies show that the algorithm is capable of enforcing the general notion of structural continuity, with the aquifer shape being conceptualized as an elongated, continuous and connected valley-shaped body. Our method captures the large-scale topographic features of fluvial incision into bedrock and the uncertainty in the positioning of the surface. Small-scale spatial variability is incorporated using Sequential Gaussian Simulation informed by geological analogs. Being stochastic, the methodology allows characterization of the uncertainty associated with positioning of the bedrock surface, by generating an ensemble of models via a Monte-Carlo analysis. This makes it possible to quantify the uncertainty associated with estimating the aquifer volume. We also discuss how this methodology may be used to better quantify the influence of uncertainty associated with defining the aquifer geometry on water resource assessment and management.