Gravitational waves (GWs) from merging black holes allow for unprecedented probes of strong-field gravity. Testing gravity in this regime requires accurate predictions of gravitational waveform templates in viable extensions of General Relativity. We concentrate on scalar Gauss-Bonnet gravity, one of the most compelling classes of theories appearing as low-energy limit of quantum gravity paradigms, which introduces quadratic curvature corrections to gravity coupled to a scalar field and allows for black hole solutions with scalar-charge. Focusing on inspiralling black hole binaries, we compute the leading-order corrections due to curvature nonlinearities in the GW and scalar waveforms, showing that the new contributions, beyond merely the effect of scalar field, appear at first post-Newtonian order in GWs. We provide ready-to-implement GW polarizations and phasing. Computing the GW phasing in the Fourier domain, we perform a parameter-space study to quantify the detectability of deviations from General Relativity. Our results lay important foundations for future precision tests of gravity with both parametrized and theory-specific searches.