Symbioses between eukaryotic algae and nitrogen-fixing cyanobacteria have been recognized in recent years as a key source of new nitrogen in the oceans. We investigated the composition of the small photosynthetic eukaryote communities associated with nitrogen-fixing cyanobacteria in the Brazilian South Atlantic Bight using a combination of flow cytometry sorting and high throughput sequencing of two genes: the V4 region of 18S rRNA and nifH. Two distinct eukaryotic communities were often encountered, one dominated by the Mamiellophyceae Bathycoccus and Ostreococcus, and one dominated by a prymnesiophyte known to live in symbiosis with the UCYN-A1 nitrogen-fixing cyanobacterium. Among nifH sequences, those from UCYN-A1 were most abundant but three other UCYN-A clades (A2, A3, A4) were also found. Network analysis confirmed the relation between A1 and A2 clades and their hypothesized hosts and pointed out to the potential association between novel clade A4 with Braarudosphaera bigelowii, previously hypothesized to host A2.