The Brazilian melon agribusiness is in expansion, reaching almost 500 thousand tons per year and making melon the main domestic fruit in both exported volume and value, with this activity being concentrated in the Brazilian Semiarid region. However, Brazil ranks only twelfth among the producing countries in area planted and production and the twentieth-third in productivity, demonstrating that there is still much to do on melon breeding and genetic resources of this crop. Thus, the objectives of this work were to estimate the genetic diversity of melon accessions collected from the traditional agricultural areas of the Brazilian Northeastern region by using descriptors for the fruit and microsatellite markers, and to study the nature of genotype vs. environment interaction and to estimate genetic parameters and gains by selection of melon families, in the Jaguaribe/Assú irrigation projects (Ceará and Rio Grande do Norte States, Brazil). The study of genetic diversity showed great variability among accessions, within and among the botanical groups, enabling advances in genetic improvement of fruit quality traits. Cluster analysis by fruit descriptors formed eight groups, without taxonomic criteria. The characters fruit longitudinal diameter, number of fruits per plant, cavity thickness and total soluble solids were descriptors that contributed most to the dissimilarity of the genotypes. The SSR markers amplified 41 alleles with average of 2.41 alleles and three genotypes per locus. A phylogenetic molecular analysis separated the accessions into 13 groups, also without taxonomic coherence in groups formed. The degree of association between genetic distance morpho-agronomic and molecular matrices was null. Then, there was no significant association between the descriptors and SSR markers, which was predictable due the number of distinct groups, the quantitative nature of the descriptors and the distribution of SSR markers in the genome. In the study of genotype vs. environment interaction, there was heterogeneity among the families for all traits. Heritability estimates in the combined analysis were consistently lower than those estimated for each environment. The simple part of G vs. E interaction was always above 99%, except for pulp firmness, with a predominance of the large complex part between the pairs of environments A1 and A3 and A2 and A3. The direct gains by selection were higher than the indirect gains for all traits in all environments evaluated. Gains were closer to the direct genetic gains when the selection was based on the average of the three environments. Estimates of genetic parameters associated with the simple nature of the family vs. environment interaction allowed genetic progress by simple breeding methods. As the genotype-environment interaction overestimates the coefficient of genetic variation and genetic variance among families in an environment, genotype assessments in more than one location are necessary since that selection is made considering the average of the families on the environments. Therefore, the potential of genetic improvement was demonstrated for the germplasm used in the study of genetic diversity as well as for the germplasm evaluated in the analysis of genotype-environment interaction.