The interannual variability of the exchange flow between the Red Sea and the Gulf of Aden through the Bab-al-Mandeb strait is examined based on a high-resolution, nonhydrostatic hindcast model simulation covering a 19-year period (1995–2013), using the MITgcm (MIT general circulation model). The model is validated against moored profiles and along-strait cruise observations collected during the period from June 1995 to November 1996 and 19-year sea surface temperature satellite observations. The model well reproduces the properties of the water masses at the strait over a wide range of spatiotemporal scales, including the typical two- and three-layer seasonal patterns and the related intraseasonal-to-interannual cycles. The seasonality of the exchange flow is predominately determined by the time-varying surface winds, with a higher correlation over the Gulf of Aden, reflecting the importance of local Gulf of Aden processes for the exchanges at the strait. The alternation of the two seasonal patterns is driven by a combination of the buoyancy-driven mean circulation with the wind-induced transport. The onset/offset of the two patterns is estimated to take place one-to-two weeks after the respective monsoon-driven wind reversal. Model results indicate that the onset dates and durations of both patterns exhibit a considerable interannual variability. Additionally, the duration of the summer (winter) exchange pattern presents a significant increasing (decreasing) trend of ~1.45 day/year (~1.22 day/year) over the 19-year period. Significant interannual variabilities and trends are observed in terms of the total volume of water, salt mass, and stored heat of the exchanges. Budget analysis of these trends suggests that the duration of the two exchange patterns is more important in determining the interannual variability and the related trends than the intensity of the exchange, or the variations in mean salinity or temperature of the exchanged water masses.