Prokaryotic epiphytes on leaves of three seagrass species, Thalassodendron ciliatum, Thalassia hemprichii, and Cymodocea rotundata, from two Kenyan coastal sites, Nyali (a high-nutrient site) and Vipingo (a low-nutrient site), were characterized genetically and morphologically. Denaturing gradient gel electrophoresis (DGGE) and clone libraries of PCR-amplified 16S rRNA gene fragments were used to study prokaryotes associated with these seagrasses. In general, the epiphytic coverage was greater in the high-nutrient site, while the microbial diversity was linked to seagrass species rather than the study sites. Cytophaga-Flavobacteria-Bacteroides (CFB) were associated with T. ciliatum and T. hemprichii mainly in the nutrient-poor site, while alpha-, beta-, and gamma-proteobacteria were associated with all three species at the two study sites. Some bacteria phylotypes were closely related to sequences of microorganisms previously recovered from wastewaters or other contaminated sources, indicating the influx of land-based wastes into these coastal lagoon ecosystems. The abundance of potential nitrogen (N2)-fixing cyanobacteria on C. rotundata, particularly in the low-nutrient site, suggested that this association may have been acquired to meet N demands. Unicellular cyanobacteria were dominant and associated with C. rotundata and T. hemprichii (with those on T. hemprichii being closely related to cyanobacterial symbiotic species), while T. ciliatum was almost devoid of cyanobacterial associations at the same site (Nyali), which suggests specificity in the cyanobacteria-seagrass associations. The abundance of prokaryotic epiphytes was considered to be linked to water depth and tidal exposure.