Microbial enhanced oil recovery (MEOR) is one of the most economical and efficient methods for extending the life of production wells in a declining reservoir. Microbial consortia from Wafra oil wells and Suwaihat production water, Al-Wusta region, Oman were screened. Microbial consortia in brine samples were identified using denaturing gradient gel electrophoresis and 16S rRNA gene sequences. The detected microbial consortia of Wafra oil wells were completely different from microbial consortia of Suwaihat formation water. A total of 33 genera and 58 species were identified in Wafra oil wells and Suwaihat production water. All of the identified microbial genera were first reported in Oman, with Caminicella sporogenes for the first time reported from oil fields. Most of the identified microorganisms were found to be anaerobic, thermophilic, and halophilic, and produced biogases, biosolvants, and biosurfactants as by-products, which may be good candidates for MEOR.