Integrating nanoscale electromechanical transducers and nanophotonic devices potentially can enable new acousto-optic devices to reach unprecedented high frequencies and modulation efficiency. We demonstrate acousto-optic modulation of a photonic crystal nanocavity using acoustic waves with frequency up to 19 GHz, reaching the microwave K band. Both the acoustic and photonic devices are fabricated in piezoelectric aluminum nitride thin films. Excitation of acoustic waves is achieved with interdigital transducers with periods as small as 300 nm. Confining both acoustic wave and optical wave within the thickness of the membrane leads to improved acousto-optic modulation efficiency in the new devices than that obtained in previous surface acoustic wave devices. Our system demonstrates a novel scalable optomechanical platform where strong acousto-optic coupling between cavity-confined photons and high frequency traveling phonons can be explored.