We present an experimental study of spin-torque driven vortex self-oscillations in magnetic nanocontacts. We find that, above a certain threshold in applied currents, the vortex gyration around the nanocontact is modulated by relaxation oscillations, which involve periodic reversals of the vortex core. This modulation leads to the appearance of commensurate but also, more interestingly here, incommensurate states, which are characterized by devil's staircases in the modulation frequency. We use frequency- and time-domain measurements together with advanced time-series analyses to provide experimental evidence of chaos in incommensurate states of vortex oscillations, in agreement with theoretical predictions.