Flavor is a key attribute defining melon fruit quality and driving consumer preferences. We characterized and compared fruit ripening patterns (ethylene, respiration), physicochemical properties (rind/flesh color, firmness, soluble solids, acidity), aroma volatiles, and flavor-related sensory attributes in seven melon genotypes differing in shelf life capacity. Fruits were evaluated at optimal maturity and after storage for six days at 5 °C plus one day at room temperature. Total volatile content increased after storage in all genotypes, with esters being dominant. Shorter shelf-life genotypes, displaying a sharper climacteric phase, correlated with fruity/floral/sweet flavor-related descriptors, and with esters, sulfur-containing compounds and a terpenoid. Longer shelf-life types were associated with firmness, green and grassy aroma/flavor and aldehydes. Multivariate regression identified key volatiles that predict flavor sensory perception, which could accelerate breeding of longer shelf-life melons with improved flavor characteristics.