In spite of increasing public health concerns about the potential risks associated with swimming in waters contaminated with waterfowl feces, little is known about the composition of the gut microbial community of aquatic birds. To address this, a gull 16S rRNA gene clone library was developed and analyzed to determine the identities of fecal bacteria. Analysis of 282 16S rRNA gene clones demonstrated that the gull gut bacterial community is mostly composed of populations closely related to Bacilli (37%), Clostridia (17%), Gammaproteobacteria (11%), and Bacteriodetes (1%). Interestingly, a considerable number of sequences (i.e., 26%) were closely related to Catellicoccus marimammalium, a gram-positive, catalase-negative bacterium. To determine the occurrence of C. marimammalium in waterfowl, species-specific 16S rRNA gene PCR and real-time assays were developed and used to test fecal DNA extracts from different bird (n = 13) and mammal (n = 26) species. The results showed that both assays were specific to gull fecal DNA and that C. marimammalium was present in gull fecal samples collected from the five locations in North America (California, Georgia, Ohio, Wisconsin, and Toronto, Canada) tested. Additionally, 48 DNA extracts from waters collected from six sites in southern California, Great Lakes in Michigan, Lake Erie in Ohio, and Lake Ontario in Canada presumed to be impacted with gull feces were positive by the C. marimammalium assay. Due to the widespread presence of this species in gulls and environmental waters contaminated with gull feces, targeting this bacterial species might be useful for detecting gull fecal contamination in waterfowl-impacted waters.