We demonstrate the blue InGaN/GaN multiple quantum wells light-emitting diodes (LEDs) with an embedded air-gap photonic crystal (PC) which was fabricated by the lateral epitaxial overgrowth of GaN layer on the tungsten (W) nano-masks. The periodic air-gap PC was formed by the chemical reaction of hydrogen with GaN on the W nano-mask. The optical output power of LEDs with an air-gap PC was increased by 26% compared to LEDs without an air-gap PC. The enhanced optical output power was attributed to the improvement in internal quantum efficiency and light extraction efficiency by the air-gap PC embedded in GaN layer.