In this paper we present the results of a coherent narrow-band search for continuous gravitational-wave signals from the Crab and Vela pulsars conducted on Virgo VSR4 data. In order to take into account a possible small mismatch between the gravitational-wave frequency and two times the star rotation frequency, inferred from measurement of the electromagnetic pulse rate, a range of 0.02 Hz around two times the star rotational frequency has been searched for both the pulsars. No evidence for a signal has been found and 95% confidence level upper limits have been computed assuming both that polarization parameters are completely unknown and that they are known with some uncertainty, as derived from x-ray observations of the pulsar wind torii. For Vela the upper limits are comparable to the spin-down limit, computed assuming that all the observed spin-down is due to the emission of gravitational waves. For Crab the upper limits are about a factor of 2 below the spin-down limit, and represent a significant improvement with respect to past analysis. This is the first time the spin-down limit is significantly overcome in a narrow-band search.