We designed, fabricated and tested gallium phosphide (GaP) nano-waveguides for second harmonic generation (SHG). We demonstrate SHG in the visible range around 655 nm using low power continuous-wave pump in the optical communication O-band. Our structures utilize modal phase matching, such that lower order eigenmodes of the pump are phase matched to higher order eigenmodes of the second harmonic. We observe phase matched SHG for different combinations of interacting modes by varying the widths of the waveguides and tuning the wavelength of the pump. The presented results contribute to the development of integrated photonic platforms with efficient nonlinear wave-mixing processes for classical and quantum applications.