One of the most interesting developments in the field of modern-day microbiology is the ever increasing number of whole-genome sequences that is publicly available. There is an increasing interest in the use of these genome sequences to assess evolutionary relationships among microbial taxa, as it is anticipated that much additional taxonomic information can be extracted from these sequences. In a first part of the present review, mechanisms that are responsible for the evolution of genomes will be discussed. Subsequently, we will give an overview of approaches that are presently available to assess the taxonomic relationships between prokaryotic species based on complete genome sequences, followed by a brief discussion of the potential implications of these novel approaches for bacterial taxonomy in general and our thinking about the bacterial species concept in particular.