We examine the dependence of parton distribution functions (PDFs) on the value of the QCD coupling strength $\alpha_{s}(M_{Z})$. We explain a simple method that is rigorously valid in the quadratic approximation normally applied in PDF fitting, and fully reproduces the correlated dependence of theoretical cross sections on $\alpha_s$ and PDF parameters. This method is based on a statistical relation that allows one to add the uncertainty produced by $\alpha_s$, computed with some special PDF sets, in quadrature with the PDF uncertainty obtained for the fixed $\alpha_s$ value (such as the CTEQ6.6 PDF set). A series of four CTEQ6.6AS PDFs realizing this approach, for $\alpha_s$ values in the interval $0.116 \leq \alpha_{s}(M_{Z}) \leq 0.120$, is presented. Using these PDFs, the combined $\alpha_{s}$ and PDF uncertainty is assessed for theoretical predictions at the Fermilab Tevatron and Large Hadron Collider.