We find that spontaneously broken parity (P) or left-right symmetry stabilizes dark matter in a beautiful way. If dark matter has a non-real intrinsic parity \pm i (e.g. Majorana fermions), parity can ensure that it cannot decay to all normal particles with real intrinsic parities. However if Majorana couplings are absent either in the Lepton or the dark sector, P symmetry can be redefined to remove relative non-real intrinsic phases. It is therefore predicted that neutrinos and dark matter fermions must have Majorana masses if dark matter is stable due to parity. We also consider vectorlike doublet fermions with intrinsic parity \pm i. Strong CP problem is solved by additionally imposing CP. Leptonic CP phases vanish at the tree level in the minimal strong CP solving model, which is a testable prediction. Experimentally if leptonic CP phases are not found (they are found to be consistent with 0 or \pi) it can be evidence for the type of models in this work where CP is spontaneously or softly broken and there is also a second hidden or softly broken symmetry such as P, Z_2 or Z_4. However leptonic CP violation can be present in closely related or some non-minimal versions of these models.