Tidal heterolithic sandstones are commonly characterized by millimeter- to centimeter-scale intercalations of mudstone and sandstone. Consequently, their effective flow properties are poorly predicted by (1) data that do not sample a representative volume or (2) models that fail to capture the complex three-dimensional architecture of sandstone and mudstone layers. We present a modeling approach in which surfaces are used to represent all geologic heterogeneities that control the spatial distribution of reservoir rock properties (surface-based modeling). The workflow uses template surfaces to represent heterogeneities classified by geometry instead of length scale. The topology of the template surfaces is described mathematically by a small number of geometric input parameters, and models are constructed stochastically. The methodology has been applied to generate generic, three-dimensional minimodels (9 m3 volume) of cross-bedded heterolithic sandstones representing trough and tabular cross-bedding with differing proportions of sandstone and mudstone, using conditioning data from two outcrop analogs from a tide-dominated deltaic deposit. The minimodels capture the cross-stratified architectures observed in outcrop and are suitable for flow simulation, allowing computation of effective permeability values for use in larger-scale models. We show that mudstone drapes in cross-bedded heterolithic sandstones significantly reduce effective permeability and also impart permeability anisotropy in the horizontal as well as vertical flow directions. The workflow can be used with subsurface data, supplemented by outcrop analog observations, to generate effective permeability values to be derived for use in larger-scale reservoir models. The methodology could be applied to the characterization and modeling of heterogeneities in other types of sandstone reservoirs.