Background: The objective of this study was to evaluate if imbalance influences complication rates, radiological outcomes, and patient-reported outcomes (PROMs) following adult spinal deformity (ASD) surgery. Methods: ASD patients with baseline and 2-year radiographic and PROMs were included. Patients were grouped according to whether they answered yes or no to a recent history of pre-operative loss of balance. The groups were propensity-matched by age, pelvic incidence–lumbar lordosis (PI-LL), and surgical invasiveness score. Results: In total, 212 patients were examined (106 in each group). Patients with gait imbalance had worse baseline PROM measures, including Oswestry disability index (45.2 vs. 36.6), SF-36 mental component score (44 vs. 51.8), and SF-36 physical component score (p < 0.001 for all). After 2 years, patients with gait imbalance had less pelvic tilt correction (−1.2 vs. −3.6°, p = 0.039) for a comparable PI-LL correction (−11.9 vs. −15.1°, p = 0.144). Gait imbalance patients had higher rates of radiographic proximal junctional kyphosis (PJK) (26.4% vs. 14.2%) and implant-related complications (47.2% vs. 34.0%). After controlling for age, baseline sagittal parameters, PI-LL correction, and comorbidities, patients with imbalance had 2.2-times-increased odds of PJK after 2 years. Conclusions: Patients with a self-reported loss of balance/unsteady gait have significantly worse PROMs and higher risk of PJK.