Cucumber (Cucumis sativus L.) has served as the model system for sex expression in flowering plants and its sex type is predominantly controlled by two genetic loci, F and M. Ethylene is the major plant hormone that regulates sex expression in cucumber. The current model predicts that ethylene serves as both a promoter of femaleness via the F locus and an inhibitor of the male sex via the M locus. In support of this model, genetic, genomic, and transcript analyses indicate that the F gene encodes a key enzyme in ethylene biosynthesis. In this study, we discovered that the M locus co-segregates with an ETHYLENE-INSENSITIVE3 (EIN3)-like genomic sequence in an F2 population of 96 individuals. This genetic association agrees with the prediction that the M locus is involved in ethylene signaling, thus providing another line of evidence in favor of the model. In addition, we generated an amplified fragment length polymorphism (AFLP) map of the M locus, which was delimited into a genetic interval of 2.5 cM. The genetic association and the local map will assist the molecular isolation of the M gene using the combination of positional cloning and candidate gene approach.