The Upper formation of Aeolis Mons in Gale crater exhibits curvilinear bedding patterns on the surfaces of several erosional benches that have been interpreted as cross-bedding. We use High Resolution Imaging Science Experiment (HiRISE) stereo topography to test this hypothesis by measuring the bedding geometry within these benches. The bedding geometry is consistent with aeolian cross-beds: measured dips rarely exceed the angle of repose, and the distribution of dip azimuths is non-random, allowing dune morphology and paleo-transport directions to be inferred using computer models of bedforms. The inferred dune type and transport direction vary between the benches of the Upper formation, indicating that the benches are separated by sufficient time for the wind regime to change. The paleo-wind directions derived from bedding geometry measurements differ from modern wind modeling results, suggesting that the conditions during deposition of the Upper formation were unlike modern conditions. The concentric bedding patterns in some locations indicate that the rate of deposition approached the rate of bedform migration. The evidence for lithified hundred-meter-scale dunes in the Upper formation of Aeolis Mons indicates that the area was a sediment sink at the time of formation, and any hypothesis for the formation of Aeolis Mons must be compatible with these results. We present one possible sequence of events for the formation of Aeolis Mons.