Selenium status of the Danish population is below that assumed optimal for the suggested protective effects against chronic diseases, including certain cancers. Fish and shellfish are important dietary sources of selenium in Denmark. We investigated the effect of increased fish and mussel intake on selenium blood concentrations in a population with relatively low habitual dietary selenium intake. We randomly assigned 102 healthy men and women (all non-smokers) aged 48–76 years to an intervention group (n = 51) or a control group (n = 51). Intervention participants received 1000 g fish and mussels/week for 26 weeks (~50 μg selenium/day). Controls received no intervention. Non-fasting blood samples were taken and whole blood selenium was determined using inductively coupled plasma-mass spectrometry (ICP-MS), and plasma selenoprotein P (SelP) was determined by high performance liquid chromatography coupled to ICP-MS. All available observations were included in linear multiple regression analysis to evaluate the effect of the intervention. The difference in mean change for intervention compared with control persons was 14.9 ng/mL (95% CI: 10.2, 19.7) for whole blood selenium, and 7.0 ng/mL (95% CI: 3.1, 10.9) for plasma SelP (Weeks 0–26). Selenium concentrations were significantly increased after 26 weeks of intervention, albeit to a lower degree than expected.