The Gallup Sandstone represents one of a few regressive facies of a succession of Upper Cretaceous regressive-transgressive clastic wedges in northwest New Mexico. In the Gallup sag, the formation overlies the Mancos Shale and underlies and intertongues with the Crevasse Canyon Formation, and may be grouped vertically into lower sandstone-dominated, middle coal-bearing, and upper sandstone-dominated lithofacies intervals. The lower sandstone-dominated lithofacies interval represents delta-front, barrier, and tidal environments. This lithofacies grades upward into the coal-bearing lithofacies interval that represents delta-plain and coastal-plain environments. Peat coals were formed in swamps in both interdistributary and floodplain areas; however, the thickest accumulations were in swamps associated with detrital-free, abandoned channel, and interchannel areas in the lower and upper delta-plain environments. The coal-bearing lithofacies is overlain unconformably by the upper sandstone-dominated lithofacies interval, which is interpreted as deposits of an alluvial valley drained by braided rivers passing downstream into rivers having meandering and straight channels. These lithofacies intervals record the evolution of a northeast-prograding fluvial system that drained the coastal plain and alluvial valley along the southwestern margin of the Western Interior, Late Cretaceous seaway.