Star formation on galactic scales is known to be a slow process, but whether it is slow on smaller scales is uncertain. We cross-correlate 5469 giant molecular clouds (GMCs) from a new all-sky catalog with 256 star-forming complexes (SFCs) to build a sample of 191 SFC-GMC complexes-collections of multiple clouds each matched to 191 SFCs. The total mass in stars harbored by these clouds is inferred from WMAP free-free fluxes. We measure the GMC mass, the virial parameter, the star formation efficiency {epsilon} and the star formation rate per freefall time {epsilon}_ff_. Both {epsilon} and {epsilon}_ff_ range over 3-4 orders of magnitude. We find that 68.3% of the clouds fall within {sigma}_log{epsilon}_=0.79+/-0.22dex and {sigma}_log{epsilon}_ff__=0.91+/-0.22dex about the median. Compared to these observed scatters, a simple model with a time-independent {epsilon}_ff_ that depends on the host GMC properties predicts {sigma}_log{epsilon}_ff__=0.12-0.24. Allowing for a time-variable {epsilon}_ff_, we can recover the large dispersion in the rate of star formation. This strongly suggests that star formation in the Milky Way is a dynamic process on GMC scales. We also show that the surface star formation rate profile of the Milky Way correlates well with the molecular gas surface density profile.