We present NuSTAR observations of Vela X-1, a persistent, yet highly variable, neutron star high-mass X-ray binary (HMXB). Two observations were taken at similar orbital phases but separated by nearly a year. They show very different 3-79 keV flux levels as well as strong variability during each observation, covering almost one order of magnitude in flux. These observations allow, for the first time ever, investigations on kilo-second time-scales of how the centroid energies of cyclotron resonant scattering features (CRSFs) depend on flux for a persistent HMXB. We find that the line energy of the harmonic CRSF is correlated with flux, as expected in the sub-critical accretion regime. We argue that Vela X-1 has a very narrow accretion column with a radius of around 0.4 km that sustains a Coulomb interaction dominated shock at the observed luminosities of Lx ~ 3x10^36 erg/s. Besides the prominent harmonic line at 55 keV the fundamental line around 25 keV is clearly detected. We find that the strengths of the two CRSFs are anti-correlated, which we explain by photon spawning. This anti-correlation is a possible explanation for the debate about the existence of the fundamental line. The ratio of the line energies is variable with time and deviates significantly from 2.0, also a possible consequence of photon spawning, which changes the shape of the line. During the second observation, Vela X-1 showed a short off-state in which the power-law softened and a cut-off was no longer measurable. It is likely that the source switched to a different accretion regime at these low mass accretion rates, explaining the drastic change in spectral shape.