Current biochemical characterizations of cystic fibrosis (CF) sputum do not address the high degree of microheterogeneity in the rheological properties of the mucosal matrix and only provide bulk-average particle diffusion coefficients. The viscoelasticity of CF sputum greatly reduces the diffusion rates of colloidal particles, limiting the effectiveness of gene delivery to underlying lung cells. We determine diffusion coefficients of hundreds of individual amine-modified and carboxylated polystyrene particles (diameter 100-500 nm) embedded in human CF sputum with 5 nm and 33 ms of spatiotemporal resolution. High resolution multiple particle tracking is used to calculate the effective viscoelastic properties of CF sputum at the micron scale, which we relate to its macroscopic viscoelasticity. CF sputum microviscosity, as probed by 100- and 200-nm particles, is an order of magnitude lower than its macroviscosity, suggesting that nanoparticles dispersed in CF sputum are transported primarily through lower viscosity pores within a highly elastic matrix. Multiple particle tracking provides a non-destructive, highly sensitive method to quantify the high heterogeneity of the mucus pore network. The mean diffusion coefficient becomes dominated by relatively few but fast-moving particles as particle size is reduced from 500 to 100 nm. Neutrally charged particles with a diameter <200 nm undergo more rapid transport in CF sputum than charged particles. Treatment with recombinant human DNase (Pulmozyme) reduces macroviscoelastic properties of CF sputum by up to 50% and dramatically narrows the distribution of individual particle diffusion rates but surprisingly does not significantly alter the ensemble-average particle diffusion rate.