Formaldehyde (HCHO) and nitrogen dioxide (NO₂) 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 NO₂, 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 NO₂. 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 NO₂. It has an HCHO RE of 72 ± 2% and an NO₂ RE of 96 ± 2%. This material has potential as the active component in PCDs used to reduce personal pollution exposure.