Can multilevel Monte Carlo methods improve ensemble variational data assimilation without increasing its computational cost? By shifting part of the ensemble generation cost to coarser simulation grids, larger ensemble sizes become affordable. This gives smaller sampling errors without introducing any coarse-grid bias. Numerical experiments with a quasi-geostrophic model demonstrate the potential of the approach and highlight the challenges of operational implementation.