The modulation bandwidth (f(BW)) is a critical figure-of-merit for wireless communication applications of spin torque nano-oscillators (STNOs) as it determines the maximum data rate. Although both theory and previous experiments have shown that f(BW) in STNOs is governed by the amplitude relaxation frequency f(p), we here demonstrate, using single-shot time-resolved measurements of a magnetic tunnel junction based STNO, that it can be many times larger under strong modulation. The behavior is qualitatively reproduced in macrospin simulations. Our results show that f(BW) of STNOs is not as limiting a factor for future wireless applications as previously believed.