We demonstrate second harmonic generation in photonic crystal nanocavities fabricated in the semiconductor gallium phosphide. We observe second harmonic radiation at 750 nm with input powers of only nanowatts coupled to the cavity and conversion efficiency $P_{rm out}/P_{rm in, coupled}^2 = 430%/{rm W}$. The large electronic band gap of GaP minimizes absorption loss, allowing efficient conversion. Our results are promising for integrated, low-power light sources and on-chip reduction of input power in other nonlinear processes.