In this paper we describe a super-tree approach that is able to use the information brought by hundreds of individual gene trees in order to es-tablish a reliable phylogeny of prokaryotes. Indeed, it has been often shown that the use of single genes is not sufficient to solve such a complex case. This is mainly due to problems like reconstruction artifacts, existence of hidden paralogies or the presence of numerous lateral transfers. Here, our super-tree approach allowed us to build two trees containing 86 prokaryotic organisms. All the major bacterial and archeal taxonomic groups are mono-phyletic in these trees, which present some striking differences with the classical view of prokaryotic phylogeny represented by the ribosomal RNA trees.