We analyze the relation between completely positive (CP) divisibility and the lack of information backflow for an arbitrary—not necessarily invertible—dynamical map. It is well known that CP divisibility always implies a lack of information backflow. Moreover, these two notions are equivalent for invertible maps. In this Letter, it is shown that for a map which is not invertible the lack of information backflow always implies the existence of a completely positive propagator which, however, needs not be trace preserving. Interestingly, for a wide class of image nonincreasing dynamical maps, this propagator becomes trace preserving as well, and hence, the lack of information backflow implies CP divisibility. This result sheds new light into the structure of the time-local generators giving rise to CP-divisible evolutions. We show that if the map is not invertible then positivity of dissipation/decoherence rates is no longer necessary for CP divisibility.