In this study, highly permeable rigid polyurethanes (PU) incorporating calcium oxide (CaO) (PU/CaO) composite materials were prepared via a facile and economic one-pot synthesis method and characterized for remediation of heavy metal-contaminated urban storm water run-off (USR) in a fixed-bed column. Column tests were conducted to investigate various parameters, and data were interpreted using the Bed Depth Service Time model to predict service time. Among the media tested, 25% CaO-incorporated PU (PU/CaO-25) had the highest adsorption capacity of Cu(II). PU/CaO-25 had about 2.5-fold higher rigidity (0.38 MPa) than a “typical” rigid polymer (0.15 MPa). Hydraulic conductivity tests showed PU/CaO-25 (avg. 0.4 mm) had a permeability (0.108 cm s−1) equivalent or higher than reference sands. Specific structural features of PU/CaO-25 and the remediation mechanism were also determined using FESEM/EDS, XRD, N2 gas isotherm and chemical equilibrium modeling. Moreover, column tests using simulated USR showed that all heavy metals were removed by PU/CaO-25 to below their regulation levels at ~1,100 bed volumes. Based on the physicochemical properties and functionality, PU/CaO-25 may be useful as an effective filter material in USR treatment and reuse applications.