Prediction Interval (PI) is a powerful technique for quantifying the uncertainty of regression tasks. However, research on PI for data streams has not received much attention. Moreover, traditional PI-generating approaches are not directly applicable due to the dynamic and evolving nature of data streams. This paper presents AdaPI (ADAptive Prediction Interval), a novel method that can automatically adjust the interval width by an appropriate amount according to historical information to converge the coverage to a user-defined percentage. AdaPI can be applied to any streaming PI technique as a postprocessing step. This paper develops an incremental variant of the pervasive Mean and Variance Estimation (MVE) method for use with AdaPI. An empirical evaluation over a set of standard streaming regression tasks demonstrates AdaPI’s ability to generate compact prediction intervals with a coverage close to the desired level, outperforming alternative methods.