The recent direct observation of gravitational waves (GW) from merging black holes opens up the possibility of exploring the theory of gravity in the strong regime at an unprecedented level. It is therefore interesting to explore which extensions to General Relativity (GR) could be detected. We construct an Effective Field Theory (EFT) satisfying the following requirements. It is testable with GW observations; it is consistent with other experiments, including short distance tests of GR; it agrees with widely accepted principles of physics, such as locality, causality and unitarity; and it does not involve new light degrees of freedom. The most general theory satisfying these requirements corresponds to adding to the GR Lagrangian operators constructed out of powers of the Riemann tensor, suppressed by a scale comparable to the curvature of the observed merging binaries. The presence of these operators modifies the gravitational potential between the compact objects, as well as their effective mass and current quadrupoles, ultimately correcting the waveform of the emitted GW.