Formaldehyde (HCHO) and nitrogen dioxide (NO2) often co-exist in urban environments at levels that are hazardous to health. There is a demand for a solution to the problem of their combined removal. In this paper, we investigate catalysts, adsorbents and composites for their removal efficiency (RE) toward HCHO and NO2, in the context of creating a pollution control device (PCD). Proton-transfer-reaction mass spectrometry and cavity ring-down spectrometry are used to measure HCHO, and chemiluminescence and absorbance-based monitors for NO2. Commercially available and lab-synthesized materials are tested under relevant conditions. None of the commercial adsorbents are effective for HCHO removal, whereas two metal oxide-based catalysts are highly effective, with REs of 81 ± 4% and 82 ± 1%, an improvement on previous materials tested under similar conditions. The best performing material for combined removal is a novel composite consisting of a noble metal catalyst supported on a metal oxide, combined with a treated active carbon adsorbent. The composite is theorized to work synergistically to physisorb and oxidize HCHO and chemisorb NO2. It has an HCHO RE of 72 ± 2% and an NO2 RE of 96 ± 2%. This material has potential as the active component in PCDs used to reduce personal pollution exposure.