Foot-and-mouth disease (FMD) virus serotype O has been responsible for most reported outbreaks of the disease in East Africa. A sustained campaign for the past 40 years to control FMD mainly by vaccination, combined with quarantine and zoosanitary measures has been undertaken with limited success. We investigated the genetic relationships among serotype O strains in eastern Africa using complete VP1 coding region sequences obtained from 46 FMD virus isolates collected in Kenya in the years 1964-2008 and 8 Ugandan isolates collected between 1999 and 2006. In addition, 21 selected FMDV sequences from Genbank representing reference strains from eastern Africa and elsewhere were included in the Bayesian inference analyses and the detection of selection forces. The results confirmed previous observations that eastern Africa harbours four distinct topotypes (clades with >15% sequence divergence). All but one strain isolated post-2000 belonged to topotypes EA-2, EA-3 and EA-4, while all three vaccines have been based on strains in the EA-1 topotype. The estimated dN/dS ratios across the individual codons of the entire VP1 coding region revealed that purifying (negative) selection constituted the dominant evolutionary force. Cross-border disease transmission within the region has been suggested with probable incursions of topotypes EA-3 and EA-4 into Kenya and Uganda from neighboring Ethiopia and Sudan. We conclude that the vaccines have probably been effective in controlling EA-1, but less so for the other topotypes and propose a more comprehensive representation of topotypes in the development of new vaccines in recognition of the considerable diversity and transboundary nature of serotype O.