The last interglacial period (about 125,000 years ago) is thought to have been at least as warm as the present climate. Owing to changes in the Earth's orbit around the Sun, it is thought that insolation in the Northern Hemisphere varied more strongly than today on seasonal timescales, which would have led to corresponding changes in the seasonal temperature cycle. Here we present seasonally resolved proxy records using corals from the northernmost Red Sea, which record climate during the last interglacial period, the late Holocene epoch and the present. We find an increased seasonality in the temperature recorded in the last interglacial coral. Today, climate in the northern Red Sea is sensitive to the North Atlantic Oscillation, a climate oscillation that strongly influences winter temperatures and precipitation in the North Atlantic region. From our coral records and simulations with a coupled atmosphere-ocean circulation model, we conclude that a tendency towards the high-index state of the North Atlantic Oscillation during the last interglacial period, which is consistent with European proxy records, contributed to the larger amplitude of the seasonal cycle in the Middle East.