Background: Grapes are one of the most economically important fruit crops. There are about 60 species in the genus Vitis. The phylogenetic relationships among these species are of keen interest for the conservation and use of this germplasm. We selected 309 accessions from 48 Vitis species,varieties, and outgroups, examined ~11 kb (~3.4 Mb total) of aligned nuclear DNA sequences from 27 unlinked genes in a phylogenetic context, and estimated divergence times based on fossil calibrations. Results: Vitis formed a strongly supported clade. There was substantial support for species and less for the higher-level groupings (series). As estimated from extant taxa, the crown age of Vitis was 28 Ma and the divergence of subgenera (Vitis and Muscadinia) occurred at ~18 Ma. Higher clades in subgenus Vitis diverged 16 -- 5 Ma with overlapping confidence intervals, and ongoing divergence formed extant species at 12 -- 1.3 Ma. Several species had species-specific SNPs. NeighborNet analysis showed extensive reticulation at the core of subgenus Vitis representing the deeper nodes, with extensive reticulation radiating outward. Fitch Parsimony identified North America as the origin of the most recent common ancestor of extant Vitis species. Conclusions: Phylogenetic patterns suggested origination of the genus in North America, fragmentation of an ancestral range during the Miocene, formation of extant species in the late Miocene-Pleistocene, and differentiation of species in the context of Pliocene-Quaternary tectonic and climatic change. Nuclear SNPs effectively resolved relationships at and below the species level in grapes and rectified several misclassifications of accessions in the repositories. Our results challenge current higher-level classifications, reveal the abundance of genetic diversity in the genus that is potentially available for crop improvement, and provide a valuable resource for species delineation, germplasm conservation and use.