The decreasing costs associated with next generation sequencing and related bioinformatics computing resources have facilitated the large-scale discovery of single nucleotide polymorphisms (SNPs) in crop species. In this study, the genomes of the two melon varieties CM-P01 (orange-fleshed) and MM-P02 (green-fleshed) were resequenced to identify genome-wide SNPs. A total of 2.0 Gb (CM-P01) and 1.5 Gb (MM-P02) quality-filtered sequences were generated that corresponded to 9.6× and 7.2× genome coverage, respectively, relative to the melon reference genome. By comparing these sequences, we detected 534,477 SNPs between the two varieties across the genome. The number of SNPs per chromosome ranged from 30,337 (chromosome 8) to 60,832 (chromosome 1). Of these, 15,674 SNPs were identified in predicted coding sequences, of which 8057 were synonymous and 7617 were non-synonymous. Analysis of Gene Ontology associations demonstrated that the non-synonymous SNPs were present in genes encoding various molecular functions. A subset of 97 non-synonymous SNPs was randomly selected for validation via high-resolution melting analysis. Of these, 84 SNPs (86.6%) were validated using a collection of 18 varieties, including CM-P01 and MM-P02. For these SNPs, the estimates of polymorphic information content (PIC) ranged from 0.18 to 0.38 and 62 SNPs (73.8%) showed more than 0.30 of PIC. The orange-fleshed varieties were separated from the green-fleshed varieties in our collection using the 84 SNPs. These SNPs will be a useful resource for the genetic dissection of loci that are responsible for fruit-related traits, including flesh color in melon.