Black hole (BH) oscillations known as quasi-normal modes (QNMs) are one of the most important gravitational wave (GW) sources. We propose that higher perturbative order of QNMs, generated by nonlinear gravitational interaction near the BHs, are detectable and worth searching for in observations and simulations of binary BH mergers. We calculate the metric perturbations to second-order and explicitly regularize the master equation at the horizon and spatial infinity. We find that the second-order QNMs have frequencies twice the first-order ones and the GW amplitude is up to ~10% that of the first-order one. The QNM frequency would also shift blueward up to ~1%. This provides a new test of general relativity as well as a possible distance indicator.