Gene therapy has not yet improved cystic fibrosis (CF) patient lung function in human trials, despite promising preclinical studies. In the human CF lung, inhaled gene vectors must penetrate the viscoelastic secretions coating the airways to reach target cells in the underlying epithelium. We investigated whether CF sputum acts as a barrier to leading adeno-associated virus (AAV) gene vectors, including AAV2, the only serotype tested in CF clinical trials, and AAV1, a leading candidate for future trials. Using multiple particle tracking, we found that sputum strongly impeded diffusion of AAV, regardless of serotype, by adhesive interactions and steric obstruction. Approximately 50% of AAV vectors diffused >1,000-fold more slowly in sputum than in water, with large patient-to-patient variation. We thus tested two strategies to improve AAV diffusion in sputum. We showed that an AAV2 mutant engineered to have reduced heparin binding diffused twice as fast as AAV2 on average, presumably because of reduced adhesion to sputum. We also discovered that the mucolytic N-acetylcysteine could markedly enhance AAV diffusion by altering the sputum microstructure. These studies underscore that sputum is a major barrier to CF gene delivery, and offer strategies for increasing AAV penetration through sputum to improve clinical outcomes.