The initial analysis of complete genomes has suggested that horizontal gene transfer events are very frequent between microorganisms. This could potentially render the inference, and even the concept itself, of the organismal phylogeny impossible. However, a coherent phylogenetic pattern has recently emerged from an analysis of about a hundred genes, the so-called 'core', strongly suggesting that it is possible to infer the phylogeny of prokaryotes. Also, estimation of the frequency of horizontal gene transfers at the genome level in a phylogenetic context seems to indicate that it is rather low, although of significant biological impact. Nevertheless, it should be emphasized that the history of microorganisms cannot be properly represented by the phylogeny of the core, which represents only a tiny fraction of the genome. This history, even if horizontal gene transfers are rare, should be represented by a network surrounding the core phylogeny.