Mate choice for compatible genes is often based on genes of the Major Histocompatibility Complex (MHC). While MHC-based mate choice is commonly observed in female choice, male mate choice remains elusive. In particular, if males have intense paternal care and are thus the choosing sex, male choice for females with dissimilar MHC can be expected. Here, we investigated whether male mate choice relies on MHC class I genes in the sex-role reversed pipefish Syngnathus typhle. In a mate choice experiment we determined the relative importance of visual and olfactory cues by manipulating visibility and olfaction. We found that pipefish males chose females that maximize sequence-based amino acid distance between MHC class I genotypes in the offspring when olfactory cues were present. Under visual cues large females were chosen, but in the absence of visual cues the choice pattern was reversed. The use of sex-role reversed species thus revealed that sexual selection can lead to the evolution of male MHC-based mate choice based on MHC class I genes.