Heterotrophic protists are a highly diverse and biogeochemically significant component of marine ecosystems, yet little is known about their species-specific prey preferences and symbiotic interactions in situ. Here we demonstrate how these previously unresolved questions can be addressed by sequencing the eukaryote and bacterial SSU rRNA genes from individual, uncultured protist cells collected from their natural marine environment and sorted by flow cytometry. We detected Pelagibacter ubique in association with a MAST-4 protist, an actinobacterium in association with a chrysophyte and three bacteroidetes in association with diverse protist groups. The presence of identical phylotypes among the putative prey and the free bacterioplankton in the same sample provides evidence for predator-prey interactions. Our results also suggest a discovery of novel symbionts, distantly related to Rickettsiales and the candidate divisions ZB3 and TG2, associated with Cercozoa and Chrysophyta cells. This study demonstrates the power of single cell sequencing to untangle ecological interactions between uncultured protists and prokaryotes.