The Composition Vector Tree (CVTree) is a parameter-free and alignment-free method to infer prokaryotic phylogeny from their complete genomes. It is distinct from the traditional 16S rRNA analysis in both the input data and the methodology. The prokaryotic phylogenetic trees constructed by using the CVTree method agree well with the Bergey's taxonomy in all major groupings and fine branching patterns. Thus, combined use of the CVTree approach and the 16S rRNA analysis may provide an objective and reliable reconstruction of the prokaryotic branch of the Tree of Life.