There is increasing interest in the development of Coenzyme Q10 (CoQ10) ingredients appropriate for functional food formulations, due to its potential health effects. The present work reported that food proteins including milk and soy proteins can effectively perform as vehicles to remarkably improve water dispersibility, stability and even bioaccessibility of CoQ10. The improvement was mainly due to the formation of protein-CoQ10 complexes, through hydrophobic interactions. The formation of complexes with CoQ10 distinctly changed the physicochemical properties of food protein particles that seemed to be more favorable for their colloidal stability. The complexation remarkably improved the stability against UV exposure or in vitro digestion, and bioaccessibility of CoQ10. In contrast, milk proteins (sodium caseinate and whey protein concentrate) were more appropriate to perform as vehicles for improved bioaccessibility of CoQ10 than soy protein isolate. The findings provide an effective strategy to improve the delivery and bioaccessibility of CoQ10 for the formulation of functional foods enriched with CoQ10.