Stormwater with low temperatures and elevated salinity, common in areas where deicing salt is used, might affect the removal of heavy metals by plants in stormwater treatment systems such as floating treatment wetlands. This short-term study evaluated the effects of combinations of temperature (5, 15, and 25 °C) and salinity (0, 100, and 1000 mg NaCl L⁻¹) on the removal of Cd, Cu, Pb, and Zn (1.2, 68.5, 78.4, and 559 μg L⁻¹) and Cl⁻ (0, 60, and 600 mg Cl⁻ L⁻¹) by Carex pseudocyperus, C. riparia, and Phalaris arundinacea. These species had previously been identified as suitable candidates for floating treatment wetland applications. The study found high removal capacity in all treatment combinations, especially for Pb and Cu. However, low temperatures decreased the removal of all heavy metals, and increased salinity decreased the removal of Cd and Pb but had no effect on the removal of Zn or Cu. No interactions were found between the effects of salinity and of temperature. Carex pseudocyperus best removed Cu and Pb, whereas P. arundinacea best removed Cd, Zu, and Cl⁻. The removal efficacy for metals was generally high, with elevated salinity and low temperatures having small impacts. The findings indicate that efficient heavy metal removal can also be expected in cold saline waters if the right plant species are used.