The presence of microplastic and carbon-based nanoparticles in the environment may have implications for the fate and effects of traditional hydrophobic chemicals. Here we present parameters for the sorption of 17 CB congeners to 10–180 µm sized polyethylene (micro-PE), 70 nm polystyrene (nano-PS), multiwalled carbon nanotubes (MWCNT), fullerene (C60), and a natural sediment in the environmentally relevant 10–5–10–1 µg L–1 concentration range. Effects of salinity and sediment organic matter fouling were assessed by measuring the isotherms in fresh- and seawater, with and without sediment present. Sorption to the “bulk” sorbents sediment organic matter (OM) and micro-PE occurred through linear hydrophobic partitioning with OM and micro-PE having similar sorption affinity. Sorption to MWCNT and nano-PS was nonlinear. PCB sorption to MWCNT and C60 was 3–4 orders of magnitude stronger than to OM and micro-PE. Sorption to nano-PS was 1–2 orders of magnitude stronger than to micro-PE, which was attributed to the higher aromaticity and surface–volume ratio of nano-PS. Organic matter effects varied among sorbents, with the largest OM fouling effect observed for the high surface sorbents MWCNT and nano-PS. Salinity decreased sorption for sediment and MWCNT but increased sorption for the polymers nano-PS and micro-PE. The exceptionally strong sorption of (planar) PCBs to C60, MWCNT, and nano-PS may imply increased hazards upon membrane transfer of these particles.