Several studies showed beneficial effects of sleep on memory performance. Slow waves, the electroencephalographic characteristic of deep sleep, reflected on the neuronal level by synchronous slow oscillations, seem crucial for these benefits. Traveling to moderate altitudes decreases deep sleep. In a randomized cross-over design healthy male subjects performed a visuo-motor learning task in Zurich (490m) and at Davos Jakobshorn (2590m) in random order. Memory performance was assessed immediately after learning, before sleep, and in the morning after a night of sleep. Sleep EEG recordings were performed during the nights. Our findings show an altitude induced reduction of sleep dependent memory performance. Moreover, this impaired sleep dependent memory performance was associated with reduced slow wave derived measures of neuronal synchronization. Our results are consistent with a critical role of slow waves for the beneficial effects of sleep on memory that is susceptible to natural environmental influences.