Melon (Cucumis melo) is one of the most important horticultural crops in Brazil. A set of 40 melon landraces representing a northeastern Brazilian variation was agronomically evaluated with 13 morphological traits and molecularly with 13 simple sequence repeat markers and compared with a set of 21 reference accessions of diverse taxonomic and geographic origins. Brazilian accessions were highly variable for seed, flowering time, fruit, and yield-related traits. However, most of them shared a monoecious sex type, a climacteric ripening behavior, and fruit that were low to medium in sugar with a high acid content, characteristics in accordance with those of Asian melons belonging to Momordica, Flexuosus, and Chate, and Far-Eastern Makuwa and Chinensis melon groups. Molecular analysis confirmed the genetic similarity of the Brazilian landraces to reference accessions from India, the Far East, and the Middle East belonging to those botanical groups. Momordica, Makuwa, and Chinensis melons are rarely found as landraces outside of this area thus suggesting that these landraces were introduced into Brazil from these regions. Our molecular results also support a high genetic diversity in the Brazilian collection [polymorphism information content (PIC) = 0.43], which is only slightly lower than that of the references (PIC = 0.59) that include most of the main horticultural groups of the two C. melo subspecies. This study shows that in Brazil, there is currently a large variability of this species maintained in the form of landraces, which are a potentially useful resource for breeding melons.