Ensemble classifier methods have been developed to learn from streaming data, and adapt to concept drift. One strategy employed to adapt to concept drift is to rank the classifiers in the ensemble based on their performance on the most recent samples. However, this strategy is problematic when the samples are coming from different portions of the sample space during different times. Data streams with unevenly distributed samples can occur in a wide variety of applications including detection of seasonally occurring weather phenomena, processing of video streams and others. In applications such as these, the uneven distribution of the data in the sample space must be accounted for in order to derive classifiers with good performance. In order to address this requirement, the Coverage Based Ensemble Algorithm (CBEA) was developed. CBEA is an incremental anytime learning algorithm designed to work on streaming data where the samples are very unevenly distributed. The CBEA algorithm keeps information about the range of data used to train each classifier, and keeps classifiers based on two factors: their coverage of the range of possible values, and their age. The CBEA algorithm is described in detail and experimental results demonstrating its utility are presented.