It is often assumed that decoherence arises as a result of the entangling interaction between a quantum system and its environment, as a consequence of which the environment effectively measures the system, thus washing away its quantum properties. Moreover, this interaction results in the emergence of a classical objective reality, as described by quantum Darwinism. In this Rapid Communication, we show that the idea that entanglement is needed for decoherence is imprecise. We propose a dynamical mixing mechanism capable of inducing decoherence dynamics on a system without creating any entanglement with its quantum environment. We illustrate this mechanism by introducing a simple and exactly solvable collisional model that combines both quantum and classical decoherence features. Interestingly, by tuning the model parameters, we can describe the same open system dynamics both with and without entanglement between system and environment. For a finite environment, we show that dynamical mixing can account for non-Markovian recoherence, even in the absence of entanglement. Our results highlight that system-environment entanglement is not necessary for decoherence or information back-flow, but plays a crucial role in the emergence of an objective reality.