Ciliates often form symbiotic associations with other microorganisms, both prokaryotic and eukaryotic. We are now starting to rediscover the symbiotic systems recorded before molecular analysis became available. Here, we provide a morphological and molecular characterization of a symbiotic association between the ciliate Paramecium tritobursaria and the yeast Rhodotorula mucilaginosa (syn. Rhodotorula rubra) isolated from a natural population. This symbiotic system demonstrates certain similarities with the symbiotic system formed by P. bursaria and its conventional endosymbionts, the zoochlorellae. Experimental infections of the endosymbiont-free P. tritobursaria and Paramecium deuterobursaria cell lines with R. mucilaginosa demonstrated that the yeast infectivity is concentration-dependent, with ciliates digesting part of the yeast cells. The endosymbiotic yeast may serve as a food reserve, providing starvation stress tolerance to the host. Since R. mucilaginosa is currently regarded as a pathogen causing opportunistic infections in immunocompromised humans, our finding gives further support to the vision that ciliates can harbor potential human pathogens and can be a vector for their dissemination.