MAX phases (M = metal, A = A-group element, X = C and/or N) are layered materials, combining metallic and ceramic attributes. They are also parent materials for the two-dimensional (2D) derivative, MXene, realized from selective etching of the A-element. In this work, we present a historical survey of MAX phase alloying to date along with an extensive theoretical investigation of MAX phase alloys (M = Sc, Y, Ti, Zr, Hf, V, Nb, Ta, Cr, Mo, W, Mn, Fe, Co, and Ni, A = Al, Ga, In, Si, Ge, Sn, Ni, Cu, Zn, Pd, Ag, Pt, and Au, and X = C). We assess both in-plane chemical ordering (in the so-called i-MAX phases) and solid solution. Out of the 2702 compositions, 92 i-MAX and 291 solid solution MAX phases are predicted to be thermodynamically stable. A majority of these have not yet been experimentally reported. In general, i-MAX is favored for a smaller size of A and a large difference in metal size, while solid solution is favored for a larger size of A and with comparable size of the metals. The results thus demonstrate avenues for a prospective and substantial expansion of the MAX phase and MXene chemistries.