Proteins could alter carotenoid bioaccessibility through altering their fate during digestion, due to emulsifying properties of resulting peptides, or influencing access of digestion enzymes to lipid droplets. In this investigation, we studied whether whey protein isolate (WPI), soy protein isolate (SPI), sodium caseinate (SC) and gelatin (GEL), added at various concentrations (expressed as percentage of recommended dietary allowance (RDA): 0, 10, 25 and 50%) would influence the bioaccessibility of lycopene, β-carotene or lutein, added as pure carotenoids solubilized in oil, during simulated gastro-intestinal (GI) digestion. Protein and lipid digestion as well as selected physico-chemical parameters including surface tension, ζ-potential and micelle size were evaluated. Adding proteins influenced positively the bioaccessibility of β-carotene, by up to 189% (p < 0.001), but it resulted in generally decreased bioaccessibility of lutein, by up to 50% (p < 0.001), while for lycopene, the presence of proteins did not influence its bioaccessibility, except for a slight increase with WPI, by up to 135% (p < 0.001). However, the effect depended significantly on the type of protein (p < 0.001) and its concentration (p < 0.001). While β-carotene bioaccessibility was greatly enhanced in the presence of SC, compared to WPI and GEL, the presence of SPI strongly decreased carotenoid bioaccessibility. Neglecting individual carotenoids, higher protein concentration correlated positively with carotenoid bioaccessibility (R = 0.57, p < 0.01), smaller micelle size (R = -0.83, p < 0.01), decreased repulsive forces (ζ-potential, R = -0.72, p < 0.01), and higher surface tension (R = 0.44, p < 0.01). In conclusion, proteins differentially affected carotenoid bioaccessibility during digestion depending on carotenoid and protein species, with both positive and negative interactions occurring.