Photonic crystal nanocavities at visible wavelengths are fabricated in a high refractive index (n>3.2) gallium phosphide membrane. The cavities are probed via a cross-polarized reflectivity measurement and show resonances at wavelengths as low as 645 nm at room temperature, with quality factors between 500 and 1700 for modes with volumes 0.7(lambda/n)^3. These structures could be employed for submicron scale optoelectronic devices in the visible, and for coupling to novel emitters with resonances in the visible such as nitrogen vacancy centers, and bio- and organic molecules.