Cellular Automata (CA) is an evolutionary computing technique that makes discrete idealizations of differential equations and represents the physical system at the mesoscopic scale. A novel CA approach for predicting the temporal and spatial variations of chlorine in Water Distribution Systems (WDSs) is presented in this paper. Random Walk Particle Tracking (RWPT), a stochastic Lagrangian technique, is used to represent the advection and dispersion processes. A one-dimensional CA-based reactive-transport model for chlorine, named as RWPT_CA model, incorporating advective-dispersive transport mechanism is developed and demonstrated. The significance of the cell dimension in the model algorithm is ascertained, and a deterministic approach is formulated for its selection. An indirect numerical solution technique is developed to improve the computational efficiency of the CA algorithm and to minimize the restrictions in the process of discretization of mass into equivalent particles. The numerical accuracy of the proposed RWPT_CA model is verified by applying it on to a benchmark problem. The RWPT_CA model provided excellent representations of the chlorine concentration profiles for low to medium range dispersion in WDSs. The model testing on a benchmark problem from the literature, well tested by researchers, revealed its effectiveness to derive the chlorine concentration patterns under dynamic hydraulic conditions. The dispersion mechanism was found significant in controlling the temporospatial distribution of chlorine at the nodes farther from the source nodes. The models which consider only advective transport mechanism were found over-predicting the chlorine concentrations, and thereby, establishing untrue representations of the quality of the delivered water. © 2020, Springer Nature Switzerland AG.