Cigarette smoke first interacts with the lung through the cellularly diverse airway epithelium and goes on to drive development of most chronic lung diseases. Here, through single cell RNA-sequencing analysis of the tracheal epithelium from smokers and non-smokers, we generate a comprehensive atlas of epithelial cell types and states, connect these into lineages, and define cell-specific responses to smoking. Our analysis infers multi-state lineages that develop into surface mucus secretory and ciliated cells and then contrasts these to the unique specification of submucosal gland (SMG) cells. Accompanying knockout studies reveal that tuft-like cells are the likely progenitor of both pulmonary neuroendocrine cells and CFTR-rich ionocytes. Our smoking analysis finds that all cell types, including protected stem and SMG populations, are affected by smoking through both pan-epithelial smoking response networks and hundreds of cell-specific response genes, redefining the penetrance and cellular specificity of smoking effects on the human airway epithelium.