In this study, we report on first 16S rRNA gene sequences from highly saline brine sediments taken at a depth of 1,515 m in the Kebrit Deep, northern Red Sea. Microbial DNA extracted directly from the sediments was subjected to PCR amplification with primers specific for bacterial and archaeal 16S rRNA gene sequences. The PCR products were cloned, and a total of 11 (6 bacterial and 5 archaeal) clone types were determined by restriction endonuclease digestion. Phylogenetic analysis revealed that most of the cloned sequences were unique, showing no close association with sequences of cultivated organisms or sequences derived from environmental samples. The bacterial clone sequences form a novel phylogenetic lineage (KB1 group) that branches between the Aquificales and the Thermotogales. The archaeal clone sequences group within the Euryarchaeota. Some of the sequences cluster with the group II and group III uncultivated archaea sequence clones, while two clone groups form separate branches. Our results suggest that hitherto unknown archaea and bacteria may thrive in highly saline brines of the Red Sea under extreme environmental conditions.