The aim of the present study was to explore age-related sleep alterations in normal subjects whose sleep had been recorded for the first time 40.4 ± 4.8 years ago. For the follow-up polysomnography (3 nights) 15 participants (5 female, 10 male, age 56–74 years) were recruited. Recording conditions and sleep scoring were adapted to the previous study. In all older participants, the amount of slow-wave sleep and REM sleep was decreased, while stage 1 and wakefulness were increased. There was no significant change in stage 2 or in any of the additional REM sleep parameters (REM density, latency, number and duration of REM cycles). Sleep stage transition analysis showed a markedly reduced stability of SWS from young to older age. While none of the single sleep parameters showed intra-individual stability with age, a pattern analysis, which combined seven sleep parameters (sleep stages, total sleep time and REM density), showed that the concordance rate of the combined sleep parameters correlated significantly with the age at follow-up. The results of this longitudinal study over a period of about 40 years are largely consistent with those of cross-sectional studies. While the lack of significant correlation of the individual sleep parameters between the younger and older age groups did not allow for the identification of any of them as trait markers, the result of the pattern analysis, which combined a set of sleep parameters, indicates that the stability of the sleep structure decreases significantly in the age range between the late 50s and early 70s.