Recent molecular data on the maternally inherited mitochondrial (mt) DNA have challenged the traditional view that the now extinct Baltic sturgeon population belonged to the European sturgeon Acipenser sturio. Instead, there is evidence that American sea sturgeon Acipenser oxyrinchus historically immigrated into the Baltic Sea. In this study, we test the hypothesis that A. oxyrinchus introgressed into, rather than replaced, the A. sturio population in the Baltic. We established four single nucleotide polymorphisms (SNPs) in the nuclear MHC II antigen gene with a species-specific SNP pattern. Using an ancient DNA approach and two independent lines of molecular evidence (sequencing of allele-specific clones, SNaPshot), we detected both A. sturio and A. oxyrinchus alleles in the available museum material of the now extinct Baltic sturgeon population. The hybrid nature of the Baltic population was further confirmed by very high levels of heterozygosity. It had been previously postulated that the immigration of the cold-adapted A. oxyrinchus into the Baltic occurred during the Medieval Little Ice Age, when temperature likely dropped below the degree inducing spawning in A. sturio. Under this scenario, our new findings suggest that the genetic mosaic pattern in the Baltic sturgeon population (oxyrinchus mtDNA, sturio and oxyrinchus MHC alleles) is possibly caused by sex-biased introgression where spawning was largely restricted to immigrating American females, while fertilization was predominantly achieved by abundant local European males. The hybrid nature of the former Baltic sturgeon population should be taken into account in the current reintroduction measures.