Little is known about the genetic relationships between European and other Old-World strains of West Nile virus (WNV) and persistence of WNV North of Mediterranean. We characterized the complete genomes of three WNV strains from France (horse-2000), Tunisia (human-1997) and Kenya (mosquito-1998), and the envelope, NS3 and NS5 genes of the Koutango virus. Phylogenetic analyses including all available full-length sequences showed that: (1) Koutango virus is a distant variant of WNV; (2) the three characterized strains belong to lineage 1, clade 1a; (3) the Tunisian strain roots the lineage of viruses introduced in North America. We established that currently available partial envelope sequences do not generate reliable phylogenies. Accordingly, establishing a large WNV sequence database is pivotal for the understanding of spatial and temporal epidemiology of this virus. For rapid completion of that purpose, colinearized E-NS3-NS5 gene sequences were shown to constitute a valuable surrogate for complete sequences.