This paper evaluates the contribution of (i) uncertainty in substance properties, (ii) lack of spatial variability, (iii) intermodel differences and (iv) neglecting sorption to black carbon (BC) to the uncertainty of Benzo[a]pyrene (BaP) concentrations in European air, soil and fresh water predicted by the multi-media fate model Simplebox. Uncertainty in substance properties was quantified using probabilistic modeling. The influence of spatial variability was quantified by estimating variation in predicted concentrations with three spatially explicit fate models (Impact 2002, EVn BETR and BETR Global). Intermodel differences were quantified by comparing concentration estimates of Simplebox, Impact 2002, EVn BETR and the European part of BETR Global. Finally, predictions of a BC-inclusive version of Simplebox were compared with predictions of a BC-exclusive version. For air concentrations of BaP, the lack of spatial variability in emissions was most influential. For freshwater concentrations of BaP, intermodel differences and lack of spatial variability in dimensions of fresh water bodies were the dominant sources of uncertainty. For soil, all sources of uncertainty were of comparable magnitude. Our results indicate that uncertainty in Simplebox can be as large as three orders of magnitude for BaP concentrations in the environment and would be substantially underestimated by focusing on one source of uncertainty only.