Background. Phylogenies reconstructed with only one or a few independently inherited loci may be unresolved or incongruent due to taxon and gene sampling, horizontal gene transfer, or differential selection and lineage sorting at individual loci. In an effort to remedy this situation, we examined the utility of conserved orthologous set (COSII) nuclear loci to elucidate the phylogenetic relationships among 29 diploid Solanum species in the sister clades that include tomato and potato, and in Datura inoxia as a far outgroup. We screened 40 COSII markers with intron content over 60% that are mapped in different chromosomes; selected a subset of 19 by the presence of single band amplification of size mostly between 600 and 1200 bp; sequenced these 19 COSII markers, and performed phylogenetic analyses with individual and concatenated datasets. The present study attempts to provide a fully resolved phylogeny among the main clades in potato and tomato that can help to identify the appropriate markers for future studies using additional species. Results. Among potatoes, when total evidence is invoked, one single predominant history is highlighted with complete resolution within and among the three main clades. It also supports the hypothesis of the North and Central American B-genome origin of the tuber-bearing members of Solanum sect. Petota and shows a clear division between A genomes in clades 3 and 4, and B genomes in clade 1+2. On the other hand, when a prior agreement approach is invoked other potato evolutionary histories are revealed but with less support. These alternative histories could be explained by past hybridization, or fast rates of speciation. In the case of tomato, the analyses with all sequence data completely resolved 19 of 21 clades, for the first time revealed the monophyly of five clades, and gave further support for the recent segregation of new species from the former Solanum peruvianum. Concordance analyses revealed and summarized the extensive discordance among COSII markers. Some potential reasons for discordance could be methodological, to include systematic errors due to using a wrong model of sequence evolution, coupled with long branches, or mixtures of branch lengths within COSII, or undetected paralogy or alignment bias. Other reasons could be biological processes such as hybridization or lineage sorting. Conclusion. This study confirms and quantifies the utility of using DNA sequences from different parts of the genome in phylogenetic studies to avoid possible bias in the sampling. It shows that 11-18 loci are enough to get the dominant history in this group of Solanum, but more loci would be needed to discern the distribution of gene genealogies in more depth, and thus detect which mechanism most likely shaped the discordance. © 2009 Rodriguez et al; licensee BioMed Central Ltd.