In this paper we present the results of the first low frequency all-sky search of continuous gravitational wave signals conducted on Virgo VSR2 and VSR4 data. The search covered the full sky, a frequency range between 20 and 128 Hz with a range of spin-down between -1.0×10-10 and +1.5×10-11 Hz/s, and was based on a hierarchical approach. The starting point was a set of short fast Fourier transforms, of length 8192 s, built from the calibrated strain data. Aggressive data cleaning, in both the time and frequency domains, has been done in order to remove, as much as possible, the effect of disturbances of instrumental origin. On each data set a number of candidates has been selected, using the FrequencyHough transform in an incoherent step. Only coincident candidates among VSR2 and VSR4 have been examined in order to strongly reduce the false alarm probability, and the most significant candidates have been selected. The criteria we have used for candidate selection and for the coincidence step greatly reduce the harmful effect of large instrumental artifacts. Selected candidates have been subject to a follow-up by constructing a new set of longer fast Fourier transforms followed by a further incoherent analysis, still based on the FrequencyHough transform. No evidence for continuous gravitational wave signals was found, and therefore we have set a population-based joint VSR2-VSR4 90% confidence level upper limit on the dimensionless gravitational wave strain in the frequency range between 20 and 128 Hz. This is the first all-sky search for continuous gravitational waves conducted, on data of ground-based interferometric detectors, at frequencies below 50 Hz. We set upper limits in the range between about 10-24 and 2×10-23 at most frequencies. Our upper limits on signal strain show an improvement of up to a factor of ∼2 with respect to the results of previous all-sky searches at frequencies below 80 Hz.