HFE-hemochromatosis is a common autosomal recessive disease caused by HFE gene mutations and characterized as iron overload and failure of different organs. The aim of this study was to determine the prevalence of C282Y (c.845 G>A), H63D (c.187 C>G), and S65C (c.193A>T) alleles of HFE gene in the Lithuanian population. One thousand and eleven healthy blood donors of Lithuanian nationality were examined in four different ethnic Lithuanian regions to determine HFE gene alleles and genotype frequencies. The samples of DNA were analyzed for the presence of restriction fragment length polymorphism and validated by DNA sequencing. Among 1,011 blood donors tested, the frequency of C282Y, H63D, and S65C alleles were 2.6%, 15.9%, and 1.9%, respectively. One third of the tested subjects (n = 336) had at least one of the C282Y or H63D HFE gene mutations. The screening of Lithuanian blood donors has detected 13 (1.3%) subjects with a genotype C282Y/C282Y or C282Y/H63D responsible for the development of HFE-hemochromatosis. The prevalence of C282Y mutation was significantly higher among the inhabitants of Zemaitija (Somogitia) at the Baltic Sea area (5.9%) in comparison to the regions of continental part of Lithuania (2.4% in Dzukija, 2.3% in Aukstaitija, and 2% in Suvalkija, p < 0.05). These data support the hypothesis that the p.C282Y mutation originated from Scandinavia and spread with the Vikings along the Baltic Sea coast. The first epidemiological investigation of HFE gene mutations in ethnic Lithuanians showed that the frequencies of H63D, C282Y, and S65C of HFE gene alleles are similar to the other North-Eastern Europeans, especially in the Baltic region (Estonia, Latvia), Poland, and part of Russia (Moscow region).