The marine picocyanobacteria Prochlorococcus represent a significant fraction of the global pelagic bacterioplankton community. Specifically, in the surface waters of the Red Sea, they account for around 91% of the phylum Cyanobacteria. Previous work suggested a widespread presence of high-light (HL)-adapted ecotypes in the Red Sea with the occurrence of low-light (LL)-adapted ecotypes at intermediate depths in the water column. To obtain a more comprehensive dataset over a wider biogeographical scope, we used a 454-pyrosequencing approach to analyze the diversity of the Prochlorococcus rpoC1 gene from a total of 113 samples at various depths (up to 500 m) from 45 stations spanning the Red Sea basin from north to south. In addition, we analyzed 45 metagenomes from eight stations using hidden Markov models based on a set of reference Prochlorococcus genomes to (1) estimate the relative abundance of Prochlorococcus based on 16S rRNA gene sequences, and (2) identify and classify rpoC1 sequences as an assessment of the community structure of Prochlorococcus in the northern, central and southern regions of the basin without amplification bias. Analyses of metagenomic data indicated that Prochlorococcus occurs at a relative abundance of around 9% in samples from surface waters (25, 50, 75 m), 3% in intermediate waters (100 m) and around 0.5% in deep-water samples (200–500 m). Results based on rpoC1 sequences using both methods showed that HL II cells dominate surface waters and were also present in deep-water samples. Prochlorococcus communities in intermediate waters (100 m) showed a higher diversity and co-occurrence of low-light and high-light ecotypes. Prochlorococcus communities at each depth range (surface, intermediate, deep sea) did not change significantly over the sampled transects spanning most of the Saudi waters in the Red Sea. Statistical analyses of rpoC1 sequences from metagenomes indicated that the vertical distribution of Prochlorococcus in the water column is correlated with physicochemical gradients: temperature and oxygen are positively correlated with HL II (R2 = 0.71, p ≤ 0.05) while Chl a concentration, nutrient concentrations and salinity correlate with the prevalence of LL clades.