An all-optically tunable microwave photonic phase shifter is demonstrated based on an epitaxial aluminum nitride (AlN) microring with an intrinsic quality factor of 3.2×106. The microring adopts a pedestal structure, which allows overcoupling with 700 nm gap size and facilitates the fabrication process. A phase shift for broadband signals from 4 to 25 GHz is demonstrated by employing the thermo-optic effect and the separate carrier tuning technique. A phase tuning range of 0°-332° is recorded with a 3 dB radio frequency (RF) power variation and 48 mW optical power consumption. In addition, AlN exhibits intrinsic second-order optical nonlinearity. Thus, our work presents a novel platform with a low propagation loss and the capability of electro-optic modulation for applications in integrated microwave photonics.