We introduce a method to construct non-Markovian variants of completely positive (CP) dynamical maps, particularly, qubit Pauli channels. We identify non-Markovianity with the breakdown in CP divisibility of the map, i.e., appearance of a not-completely positive intermediate map. In particular, we consider the case of non-Markovian dephasing in detail. The eigenvalues of the Choi matrix of the intermediate map crossover at a point which corresponds to a singularity in the canonical decoherence rate of the corresponding master equation and thus to a momentary noninvertibility of the map. Thereafter, the rate becomes negative, indicating non-Markovianity. We quantify the non-Markovianity by two methods, one based on CP divisibility [Hall, Phys. Rev. A 89, 042120 (2014)PLRAAN1050-294710.1103/PhysRevA.89.042120], which does not require optimization but requires normalization to handle the singularity, and another method, based on distinguishability [Breuer Phys. Rev. Lett. 103, 210401 (2009)PRLTAO0031-900710.1103/PhysRevLett.103.210401], which requires optimization but is insensitive to the singularity. © 2018 American Physical Society.