This paper addresses the problem of constructing reliable interval predictors directly from observed data. Differently from standard predictor models, interval predictors return a prediction interval as opposed to a single prediction value. We show that, in a stationary and independent observations framework, the reliability of the model (that is, the probability that the future system output falls in the predicted interval) is guaranteed a priori by an explicit and non-asymptotic formula, with no further assumptions on the structure of the unknown mechanism that generates the data. This fact stems from a key result derived in this paper, which relates, at a fundamental level, the reliability of the model to its complexity and to the amount of available information (number of observed data). (C) 2008 Elsevier Ltd. All rights reserved.