Effective heat dissipation is the bottleneck problem for the development and commercialization of GaN-based high-power electronic and photonic devices. To address this challenge and explore the underlying mechanism of phonon transportation across the GaN/AlN heterointerface, in this work, we formed three types of GaN/AlN heterostructures with distinctively different interfacial morphologies by annealing recrystallization approach. It is found that the interfacial thermal conductance (ITC) of GaN/AlN heterostructures can be remarkably improved by tailoring the interfacial crystal structure and phase morphology. Besides the commonly amorphous phase and ideal ordered wurtzite phase, we further found that AlN may present an additional stable rock salt phase at the interfacial region, and its significant effect on interfacial thermal transport has been observed. Using molecular dynamics simulation, we systematically investigated the effects of different GaN/AlN heterojunctions on the ITCs. Our results suggest that heat dissipation at the GaN/AlN interface is dominated by phonons scattered diffusely by the amorphous region at interfaces and the ITC can be significantly enhanced by recrystallizing the amorphous AlN to rock salt one. Furthermore, through phonon vibrational spectrum, we revealed that phonon modes dominate the energy transport across the interfaces of wurtzite AlN/GaN, amorphous AlN/GaN, and rock salt AlN/GaN are significantly different. Finally, we found the ITC increased with the temperature due to the enhanced inelastic phonon scattering and the presence of additional excited phonon modes at higher temperatures. The findings elucidated here provide a clearer insight into the effect of interfacial microstructures on the interfacial thermal resistance of GaN–substrate interface, which also provide a viable heat management strategy for the high-power GaN-based devices.