Volatile organic compounds (“VOCs”) are widely used in industrial process, transportation fuels, and households. It is inevitable that some VOCs will escape into the atmosphere. Emission of VOCs will cause three major problems, including (1) increased exposure level of the population to know carcinogenic compounds such as benzene and carbon tetrachloride, (2) increased ozone concentration in the atmosphere at ground level, and (3) stratospheric depletion of the ozone layer, which alters global climate and increases exposure to UV radiation. Reducing the concentrations of VOCs will greatly improve air quality. A common method for VOC removal is catalytic decomposition. Most works have only focus on reducing VOC concentrations down to a few parts per million (ppm). Very little research has been conducted on reducing the VOCs down to parts per billion (ppb) levels, or less. This paper reports the decomposition of VOCs using a unique class of nanofibrous bird's-nest superstructure material. This open-inter-woven nanofibrous superstructure provides superb host for catalytic reactions and permits relatively easy flow of the gas stream through the structure. The nanofibrous MnO2 is highly effective in destroy more than 50 VOCs on USEPA's top priority list toxic VOCs to ppb level or less at a 200 − 350°C temperature.