We have used deep V and R images acquired at the ESO Very Large Telescope to identify the optical companion to the binary pulsar PSR J0610-2100, one of the black-widow millisecond pulsars recently detected by the Fermi Gamma-ray Telescope in the Galactic plane. We found a faint star (V~26.7) nearly coincident (delta r ~0.28) with the pulsar nominal position. This star is visible only in half of the available images, while it disappears in the deepest ones (those acquired under the best seeing conditions), thus indicating that it is variable. Although our observations do not sample the entire orbital period (P=0.28 d) of the pulsar, we found that the optical modulation of the variable star nicely correlates with the pulsar orbital period and describes a well defined peak (R~25.6) at Phi=0.75, suggesting a modulation due to the pulsar heating. We tentatively conclude that the companion to PSR J0610-2100 is a heavily ablated very low mass star (~ 0.02Msun) that completely filled its Roche Lobe.