Polychlorinated biphenyls (PCBs) pose a threat to the environment due to their high adsorption capacity to soil organic matter, stability and low reactivity, low water solubility, toxicity and ability to bioaccumulate. With Icelandic soils, research on contamination issues has been very limited and no data has been reported either on PCB degradation potential or rate. The goals of this research were to assess the bioavailability of aged PCBs in the soils of the old North Atlantic Treaty Organization facility in Keflavík, Iceland and to find the best biostimulation method to decrease the pollution. The effectiveness of different biostimulation additives (N fertiliser, white clover and pine needles) at different temperatures (10 and 30 °C) and oxygen levels (aerobic and anaerobic) were tested. PCB bioavailability to soil fauna was assessed with earthworms (Eisenia foetida). PCBs were bioavailable to earthworms (bioaccumulation factor 0.89 and 0.82 for earthworms in 12.5 ppm PCB soil and in 25 ppm PCB soil, respectively), with less chlorinated congeners showing higher bioaccumulation factors than highly chlorinated congeners. Biostimulation with pine needles at 10 °C under aerobic conditions resulted in nearly 38 % degradation of total PCBs after 2 months of incubation. Detection of the aerobic PCB degrading bphA gene supports the indigenous capability of the soils to aerobically degrade PCBs. Further research on field scale biostimulation trials with pine needles in cold environments is recommended in order to optimise the method for onsite remediation.