Anti-MXenes are a new class of 2D materials with the formula MnXn+1, and they have recently been attracting attention. The successful synthesis of Mo5N6 and the identification of its atomic arrangements (labeled as α and γ), along with the resolved structure of TiC2, raise an important question: What are the possible atomic structures of MnXn+1 layers across different transition metals M and values of n? In this work, we identify a new structural prototype, denoted as β, through a combination of density functional theory (DFT) calculations and evolutionary optimization. By systematically exploring the stable polymorphs of 32 anti-MXenes structures with the formula MnXn+1 (M = Ti, V, Cr, Mn, Nb, Mo, Ta, and W; n = 2, 3, 4, 5), we find that the β structure is more favorable in thinner compositions (n = 2) and tends to appear at the outermost layers of thicker structures (n = 5), leading to hybrid structures that are mixtures of α/γ and β configurations. We identify a range of nontrivial electronic states in these materials: semimetals, flat bands, a semiconductor, and materials with high electronic density at the Fermi level. Further analysis of M2X3 β structures using supercell models reveals that Mo2X3 relaxes into a different lower-energy configuration. Our findings unveil the rich and complex structural and electronic landscape of anti-MXenes, which warrants further exploration of this class of materials.