We present ^12^CO(1-0) and ^12^CO(2-1) observations of a sample of 20 star-forming dwarfs selected from the Herschel Virgo Cluster Survey, with oxygen abundances ranging from 12+log(O/H)~8.1 to 8.8. CO emission is observed in ten galaxies and marginally detected in another one. CO fluxes correlate with the FIR 250um emission, and the dwarfs follow the same linear relation that holds for more massive spiral galaxies extended to a wider dynamical range. We compare different methods to estimate H_2_ molecular masses, namely a metallicity-dependent CO-to-H_2_ conversion factor and one dependent on H-band luminosity. The molecular-to-stellar mass ratio remains nearly constant at stellar masses <=10^9^M_{sun}_, contrary to the atomic hydrogen fraction, M_HI_/M*, which increases inversely with M*. The flattening of the M_H2_/M* ratio at low stellar masses does not seem to be related to the effects of the cluster environment because it occurs for both HI-deficient and HI-normal dwarfs. The molecular-to-atomic ratio is more tightly correlated with stellar surface density than metallicity, confirming that the interstellar gas pressure plays a key role in determining the balance between the two gaseous components of the interstellar medium. Virgo dwarfs follow the same linear trend between molecular gas mass and star formation rate as more massive spirals, but gas depletion timescales, tau_dep, are not constant and range between 100Myr and 6Gyr. The interaction with the Virgo cluster environment is removing the atomic gas and dust components of the dwarfs, but the molecular gas appears to be less affected at the current stage of evolution within the cluster. However, the correlation between HI deficiency and the molecular gas depletion time suggests that the lack of gas replenishment from the outer regions of the disc is lowering the star formation activity.