A semiconductor device may include a substrate, at least one memory array comprising a plurality of recessed channel array transistors (RCATs) on the substrate, and periphery circuitry adjacent the at least one memory array and including a plurality of complementary metal oxide (CMOS) transistors on the substrate. Each of the CMOS transistors may include spaced-apart source and drain regions in the substrate and defining a channel region therebetween, a superlattice extending between the source and drain regions in the channel region, and a gate over the superlattice and between the source and drain regions. The superlattice may include a plurality of stacked groups of layers, with each group of layers including a plurality of stacked base semiconductor monolayers defining a base semiconductor portion, and at least one non-semiconductor monolayer constrained within a crystal lattice of adjacent base semiconductor portions.