A recently described symbiosis between the metabolically streamlined nitrogen-fixing cyanobacterium UCYN-A and a single-celled eukaryote prymnesiophyte alga is widely distributed throughout tropical and subtropical marine waters, and is thought to contribute significantly to nitrogen fixation in these regions. Several UCYN-A sublineages have been defined based on UCYN-A nitrogenase (nifH) sequences. Due to the low abundances of UCYN-A in the global oceans, currently existing molecular techniques are limited for detecting and quantifying these organisms. A targeted approach is needed to adequately characterize the diversity of this important marine cyanobacterium, and to advance understanding of its ecological importance. We present findings on the distribution of UCYN-A sublineages based on high throughput sequencing of UCYN-A nifH PCR amplicons from 78 samples distributed throughout many major oceanic provinces. These UCYN-A nifH fragments were used to define oligotypes, alternative taxonomic units defined by nucleotide positions with high variability. The data set was dominated by a single oligotype associated with the UCYN-A1 sublineage, consistent with previous observations of relatively high abundances in tropical and subtropical regions. However, this analysis also revealed for the first time the widespread distribution of the UCYN-A3 sublineage in oligotrophic waters. Furthermore, distinct assemblages of UCYN-A oligotypes were found in oligotrophic and coastally influenced waters. This unique data set provides a framework for determining the environmental controls on UCYN-A distributions and the ecological importance of the different sublineages.