The genes of the Major Histocompatibility Complex (MHC), which plays a fundamental role in the immune system, are some of the most diverse genes in vertebrates and have been connected to mate choice in several species, including humans. While studies suggest a positive relationship between MHC diversity and male facial attractiveness, the connection of MHC diversity to other visual traits and female attractiveness is still unclear. The purpose of this study was to investigate further whether MHC heterozygosity, indicating genetic quality, is associated with visual traits affecting mate preferences in humans. In total 74 Latvian men and 49 women were genotyped for several MHC loci and rated for facial and, in men, also body attractiveness. The results indicate a preference for MHC heterozygous female and male faces. However, the initially positive relationship between MHC heterozygosity and facial attractiveness becomes non-significant in females, when controlling for multiple testing, and in males, when age and fat content is taken into account, referring to the importance of adiposity in immune function and thus also attractiveness. Thus overall the effect of MHC heterozygosity on attractiveness seems weak. When considering separate loci, we show that the main gene related to facial attractiveness is the MHC class II DQB1; a gene important also in viral infections and autoimmune diseases. Indeed, in our study, heterozygous individuals are rated significantly more attractive than their homozygous counterparts, only in relation to gene DQB1. This study is the first to indicate a link between DQB1 and attractiveness in humans.