Wide-bandgap III-nitride heterostructures are required for a variety of device applications. However, this alloy system has a large lattice constant and thermal expansion coefficient mismatch that limits the alloy composition and layer thickness for many heteroepitaxial device structures. Consequently, various methods have been devised to allow the heteroepitaxial growth of AlInGaN heterostructures to accommodate this inherent strain. In this work, we describe a non-planar-growth approach that enables the deposition of crack-free high-Al-mole-fraction AlxGa1-xN on patterned GaN/sapphire templates and bulk GaN substrates with large-area mesas. We have studied the effects of the patterned mesa width, the mesa etch depth, and the gap between the mesas on the heteroepitaxy of AlxGa1-xN superlattices with an average Al molar fraction 0.11 < x¯ < 0.21 and non-planar overgrowth growth thicknesses up to 3.5 μm. Similar to the planar growth approach, increasing the thickness and Al mole fraction of the AlxGa1-xN superlattices leads to surface cracking when exceeding the critical layer thickness. However, limiting the mesa dimension in one direction enables strain mitigation and drastically increases the critical layer thickness. Additionally, larger etch depths of the mesas increase the Al alloy composition and thickness for crack-free AlGaN heteroepitaxy whereas the gap in between the mesas seems to have no crucial influence. We demonstrate that the Al alloy composition and layer thicknesses of such heterostructures can be increased far beyond the critical layer thickness for planar growth and demonstrate the growth of a crack-free full AlxGa1-xN/GaN quantum-well laser heterostructure designed for operation at ∼370 nm.