We report on enhancing the photon-extraction efficiency (PEE) of deterministic quantum dot (QD) microlenses via anti-reflection (AR) coating. The AR-coating deposited on top of the curved microlens surface is composed of a thin layer of Ta2O5, and is found to effectively reduce back-reflection of light at the semiconductor-vacuum interface. A statistical analysis of spectroscopic data reveals, that the AR-coating improves the light out-coupling of respective microlenses by a factor of 1.57 ± 0.71, in quantitative agreement with numerical calculations. Taking the enhancement factor into account, we predict improved out-coupling of light with a PEE of up to 50%. The quantum nature of emission from QDs integrated into AR-coated microlenses is demonstrated via photon auto-correlation measurements revealing strong suppression of two-photon emission events with g(2)(0) = 0.05 ± 0.02. As such, these bright non-classical light sources are highly attractive with respect to applications in the field of quantum cryptography.