Classical novae(1,2) are thermonuclear explosions in binary stellar systems containing a white dwarf accreting material from a close companion star. They repeatedly eject 10(-4)-10(-5) solar masses of nucleosynthetically enriched gas into the interstellar medium, recurring on intervals of decades to tens of millennia. They are probably the main sources(3,4) of Galactic N-15, O-17 and C-13. The origin of the large enhancements and inhomogeneous distribution of these species observed in high-resolution spectra(5) of ejected nova shells has, however, remained unexplained for almost half a century(6). Several mechanisms(7), including mixing by diffusion(8), shear(9) or resonant gravity waves(10), have been proposed in the framework of one-dimensional or two-dimensional simulations, but none has hitherto proven successful because convective mixing can only be modelled accurately in three dimensions. Here we report the results of a three-dimensional nuclear-hydrodynamic simulation of mixing at the core-envelope interface during nova outbursts. We show that buoyant fingering drives vortices from the Kelvin-Helmholtz instability, which inevitably enriches the accreted envelope with material from the outer white-dwarf core. Such mixing also naturally produces large-scale chemical inhomogeneities. Both the metallicity enhancement and the intrinsic dispersions in the abundances are consistent with the observed values.