In order to meet the increasing demands of energy sustainability and environmental protection, catalysis science and application in the 21st century has to be driven by basic insights into how catalytic materials function and how they can be improved. The advent of first-principles simulations based on density functional theory (DFT), which are able to reliably simulate chemical structures and reactions at the molecular scale, has been instrumental in the recent renaissance in heterogeneous catalysis research. In this talk, I will illustrate the capabilities and challenges of applying these simulation tools in the context of the catalytic chemistry of nitrogen oxides (NOx). NOx is an unwanted by-product of combustion and is particularly difficult to remove from lean combustion sources, such as diesel engines. NOx also has rather complex chemistry that presents special challenges to simulation. I will describe some of our successes in understanding NOx chemistry from first-principles, with a first emphasis on recent work to capture the essential features of the beguilingly simple catalytic oxidation of NO to NO2 over metals and metal oxides, to reconcile these models with experimental results, and to use these insights to guide the selection of new and improved catalysts. I will then discuss recent work to extend the same concepts to the selective catalytic reduction of NOx over narrow-pore metal-exchanged zeolites, a new class of effective and stable catalysts.