Two activated carbons (phosphoric acid activated, CG, and steam activated, SX) of marked differences in porosity and surface chemistry were modified by an introduction of oxygen, nitrogen or both heteroatoms and used as formaldehyde removal media at room temperature. Sorption of nitrogen, XPS, FTIR, thermal analysis and potentiometric titration were used to characterize the samples’ porosity and chemistry. Heating at 450, 600 and 950 °C affected the content and speciation of groups on the surface and led to complex porosity alterations. CG was more susceptible to changes in porosity and its surface accepted twice more nitrogen than that of SX. Pyridines and pyrroles were in majority, regardless the treatment. When in a high density in supermicropores and mesopores, they were found responsible for an increased surface activity for HCHO removal due to specific interactions. It increased up to an order of magnitude adding to the complex role of ultramicropores, and thus markedly enhanced the effective utilization of the carbon surface. CG, with more nitrogen overperformed the SX series. Even though pyridines and pyrroles were found active, the results suggested that quaternary nitrogen is an important specific center for HCHO adsorption and this finding was supported by a factorial dimensionally reduction method.