A high-conductivity two-dimensional (2D) hole gas is the enabler of wide-bandgap p-channel transistors. Compared to commonly used AlN template substrates with high dislocation densities, the recently available single-crystal AlN substrates are promising to boost the speed and power handling capability of p-channel transistors based on GaN/AlN 2D hole gases (2DHGs) thanks to the much lower dislocation densities and the absence of thermal boundary resistance. Using plasma-assisted molecular beam epitaxy, we report the observation of polarization-induced high-density 2DHGs in undoped pseudomorphic GaN/AlN heterostructures on the single-crystal AlN substrates with high structural quality and atomic steps on the surface. The high-density 2DHG persists down to cryogenic temperatures with a record high mobility exceeding 280 cm2/V s and a density of 2.2 × 1013/cm2 at 10 K. These results shed light on aspects of improving 2D hole mobilities and indicate significant potential of GaN/AlN 2DHG grown on bulk AlN substrates for future high performance wide-bandgap p-channel transistors.