Rationale: The decades-long progression of chronic obstructive pulmonary disease (COPD) renders identifying different trajectories of disease progression challenging. Objectives: To identify subtypes of patients with COPD with distinct longitudinal progression patterns using a novel machinelearning tool called "Subtype and Stage Inference" (SuStaIn) and to evaluate the utility of SuStaIn for patient stratification in COPD. Methods: We applied SuStaIn to cross-sectional computed tomography imaging markers in 3,698 Global Initiative for Chronic Obstructive Lung Disease (GOLD) 1-4 patients and 3,479 controls from the COPDGene (COPD Genetic Epidemiology) study to identify subtypes of patients with COPD. We confirmed the identified subtypes and progression patterns using ECLIPSE (Evaluation of COPDLongitudinally to Identify Predictive Surrogate Endpoints) data. We assessed the utility of SuStaIn for patient stratification by comparing SuStaIn subtypes and stages at baseline with longitudinal follow-up data. Measurements and Main Results: We identified two trajectories of disease progression in COPD: a "Tissue→Airway" subtype (n = 2,354, 70.4%), in which small airway dysfunction and emphysema precede large airway wall abnormalities, and an "Airway→Tissue" subtype (n = 988, 29.6%), in which large airway wall abnormalities precede emphysema and small airway dysfunction. Subtypes were reproducible in ECLIPSE. Baseline stage in both subtypes correlated with future FEV1/FVC decline (r =20.16 [P<0.001] in the Tissue→Airway group; r =20.14 [P = 0.011] in the Airway→Tissue group). SuStaIn placed 30% of smokers with normal lung function at elevated stages, suggesting imaging changes consistent with early COPD. Individuals with early changes were 2.5 times more likely to meet COPD diagnostic criteria at follow-up. Conclusions: We demonstrate two distinct patterns of disease progression in COPD using SuStaIn, likely representing different endotypes. One third of healthy smokers have detectable imaging changes, suggesting a new biomarker of "early COPD".