The combination of nonlinear and integrated photonics enables Kerr frequency comb generation in stable chip-based microresonators. Such a comb system will revolutionize applications, including multi-wavelength lasers, metrology, and spectroscopy. Aluminum gallium arsenide (AlGaAs) exhibits very high material nonlinearity and low nonlinear loss. However, difficulties in device processing and low device effective nonlinearity made Kerr frequency comb generation elusive. Here, we demonstrate AlGaAs-on-insulator as a nonlinear platform at telecom wavelengths with an ultra-high device nonlinearity. We show high-quality-factor (Q > 105) micro-resonators where optical parametric oscillations are achieved with milliwatt-level pump threshold powers, which paves the way for on-chip pumped comb generation.