Melon is a fruit/vegetable that has been grown in Japan for at least 2000 years. To obtain a better understanding of melon crop evolution in this island country, we measured the seed size and determined the cytoplasmic genotype of 135 modern melon accessions and 12 populations of ancient melon seed remains from archaeological sites for a 2000-year period in Japan. Based on differences in seed length, populations of melon seed remains at the Shikata site (Okayama Prefecture, Japan) consisted of seed types corresponding to those of modern East and South Asian melon. Although several types of melon seeds were found in and around the Shikata site, only Agrestis-type seeds, < 6.1 mm in length, were found in melon populations from 1 CE. Intra-population length variation was higher in 1050 CE than in 1530-1680 CE. Ancient DNA from archaeological melon was analysed for SNPs in the chloroplast genome. These revealed that cytoplasm type was heterogeneous and consisted of Ia and Ib types in melon populations prior to ca. 1600 CE, and thereafter becoming homogenous by genetic erosion of Ib, which is absent in modern endemic Japanese melon accessions. The decrease in variation of both seed length and cytoplasm type together with historical records indicates that artificial selection in the Japanese melons for desired fruit traits intensified in the past 1000 years.