We report on the phase stability of chemically ordered and disordered quaternary MAX phases - TiMAlC, TiM2AlC2, MTi2AlC2, and Ti2M2AlC3 where M = Zr, Hf (group IV), M = V, Nb, Ta (group V), and M = Cr, Mo, W (group VI). At 0 K, layered chemically ordered structures are predicted to be stable for M from groups V and VI. By taking into account the configurational entropy, an order-disorder temperature Tdisorder can be estimated. TiM2AlC2 (M = Cr, Mo, W) and Ti2M2AlC3 (M = Mo, W) are found with Tdisorder > 1773 K and are hence predicted to be ordered at the typical bulk synthesis temperature of 1773 K. Other ordered phases, even though metastable at elevated temperatures, may be synthesized by non-equilibrium methods such as thin film growth. Furthermore, phases predicted not to be stable in any form at 0 K can be stabilized at higher temperatures in a disordered form, being the case for group IV, for MTi2AlC2 (M = V, Cr, Mo), and for Ti2M2AlC3 (M = V, Ta). The stability of the layered ordered structures with M from group VI can primarily be explained by Ti breaking the energetically unfavorable stacking of M and C where M is surrounded by C in a face-centered cubic configuration, and by M having a larger electronegativity than Al resulting in a fewer electrons available for populating antibonding Al-Al orbitals. The results show that these chemically ordered quaternary MAX phases allow for new elemental combinations in MAX phases, which can be used to add new properties to this family of atomic laminates and in turn prospects for tuning these properties.