Phylogenetic surveys based on cultivation-independent methods have revealed that tidal flat sediments are environments with extensive microbial diversity. Since most of prokaryotes in nature cannot be easily cultivated under general laboratory conditions, our knowledge on prokaryotic dwellers in tidal flat sediment is mainly based on the analysis of metagenomes. Microbial community analysis based on the 16S rRNA gene and other phylogenetic markers has been widely used to provide important information on the role of microorganisms, but it is basically an indirect means, compared with direct sequencing of metagenomic DNAs. In this study, we applied a sequence-based metagenomic approach to characterize uncultivated prokaryotes from tidal flat sediment. Two large-insert genomic libraries based on fosmid were constructed from tidal flat metagenomic DNA. A survey based on end-sequencing of selected fosmid clones resulted in the identification of clones containing 274 bacterial and 16 archaeal homologs in which majority were of proteobacterial origins. Two fosmid clones containing large metagenomic DNAs were completely sequenced using the shotgun method. Both DNA inserts contained more than 20 genes encoding putative proteins which implied their ecological roles in tidal flat sediment. Phylogenetic analyses of evolutionary conserved proteins indicate that these clones are not closely related to known prokaryotes whose genome sequence is known, and genes in tidal flat may be subjected to extensive lateral gene transfer, notably between domains Bacteria and Archaea. This is the first report demonstrating that direct sequencing of metagenomic gene library is useful in underpinning the genetic makeup and functional roles of prokaryotes in tidal flat sediments.