Genetic variability of marine fish species is much higher than in most other vertebrates. Nevertheless, some species with large population sizes including flatfish such as European plaice Pleuronectes platessa show signs of population collapse and inbreeding. Taking plaice as a flagship example for fisheries-induced genetic changes also affecting the Wadden Sea, we determined the amount of genetic variability at antigen-presenting genes of the Major Histocompatibility Complex (MHC) and its potential interaction with the microbiota associated to gill tissue using a next-generation parallel tag sequencing approach. Genetic variation at MHC class IIB genes was extremely large, with 97 alleles found in 40 fish from different age cohorts. Although a strong signal of positive selection was present (dN/dS = 4.01) and we found significantly higher allelic diversity in 0+ fish than in older age classes, the amount of genetic variation maintained within the population may not have exceeded neutral expectations derived from mitochondrial markers. Associated microbes revealed significant spatiotemporal structure with 0+ fish displaying the highest microbial diversity as well as the highest diversity of potentially pathogenic genera. Overall the correlation between MHC genotypes and bacterial abundance was weak, and only few alleles significantly correlated with certain bacterial genera. These associations all conferred susceptibility (i.e. presence of an allele correlated to higher number of bacteria), either suggesting age-dependent selection on common alleles or weak selection on resistance against these bacterial genera. Taken together, our data suggest that selection coefficients of balancing selection maintaining immunogenetic diversity may be relatively small in large marine populations. However, if population sizes are further reduced by overharvesting, the response to increasing balancing selection coefficients will be largely unpredictable and may also negatively influence the adaptive potential of populations.