Megacities are immense sources of air pollutants, with large impacts on air quality and climate. However, emission inventories in many of them still are highly uncertain, particularly in developing countries. Satellite observations allow top-down estimates of emissions to be made for nitrogen oxides (NOx = NO + NO2), but require poorly quantified a priori information on the NOx lifetime. We present a method for the simultaneous determination of megacity NOx emissions and lifetimes from satellite measurements by analyzing the downwind patterns of NO2 separately for different wind conditions. Daytime lifetimes are ~4 hours at low and mid-latitudes, but ~8 hours in wintertime for Moscow. The derived NOx emissions are generally in good agreement with existing emission inventories, but are higher by a factor of 3 for the Saudi Arabian capital Riyadh.