Evolving fuzzy systems (EFSs) are widely known as a powerful tool for streaming data prediction. In this paper, a novel zero-order EFS with a unique belief structure is proposed for data stream classification. Thanks to this new belief structure, the proposed model can handle the inter-class overlaps in a natural way and better capture the underlying multi-model structure of data streams in the form of prototypes. Utilizing data-driven soft thresholds, the proposed model self-organizes a set of prototype-based IF-THEN fuzzy belief rules from data streams for classification, and its learning outcomes are practically meaningful. With no requirement of prior knowledge in the problem domain, the proposed model is capable of self-determining the appropriate level of granularity for rule base construction, while enabling users to specify their preferences on the degree of fineness of its knowledge base. Numerical examples demonstrate the superior performance of the proposed model on a wide range of stationary and nonstationary classification benchmark problems.