Tremendous scientific progress has been achieved through the development of nonlinear integrated photonics. Prominent examples are Kerr frequency comb generation in microresonators, and supercontinuum generation and frequency conversion in nonlinear photonic waveguides. A high conversion efficiency is enabling for applications of nonlinear optics, including such broad directions as high-speed optical signal processing, metrology, and quantum communication and computation. In this work, a gallium-arsenide-on-insulator (GaAs) platform for nonlinear photonics is demonstrated. GaAs has among the highest second- and third-order nonlinear optical coefficients, and the use of a silica cladding results in waveguides with a large refractive index contrast and low propagation loss for expanded designs of nonlinear processes. By harnessing these properties and developing nanofabrication with GaAs, a record normalized second-harmonic efficiency of 13 000% W−1 cm−2 at a fundamental wavelength of 2 μm is reported. This work paves the way for high performance nonlinear photonic integrated circuits, which not only can transition advanced functionalities outside the lab through fundamentally reduced power consumption and footprint, but also enables future optical sources and detectors.