The Mediterranean region stands as one of the most sensitive to climate change, both in terms of warming and drying. On shorter time-scales, internal variability has substantially affected the observed climate and in the next decade might enhance or compensate long-term trends. Here we compare the multi-model climate predictions produced within the framework of the CMIP5 (Coupled Model Intercomparison Project Phase 5) project with historical simulations to assess the level of multi-year climate prediction skill in the Mediterranean region beyond that originating from the model accumulated response to the external radiative forcings. We obtain a high and significant skill in predicting 4-year averaged annual and summer mean temperature over most of the study domain and in predicting precipitation for the same seasons over northern Europe and sub-Saharan Africa. A lower skill is found during the winter season but still positive for temperature. Although most of this high skill originates from the model response to the external radiative forcings, the initialization contributes to the temperature skill over the Mediterranean Sea and surrounding land areas. The high and significant correlations between the observed Mediterranean temperatures and the observed Atlantic multidecadal oscillation (AMO) in the summer and annual means are captured by the CMIP5 ensemble which suggests that the added skill is related to the ability of the CMIP5 ensemble to predict the AMO. Such a link to the AMO seems restricted to western Africa and summer means only for the precipitation case.