A central problem in evolutionary theory concerns the mechanisms by which adaptations requiring multiple mutations emerge in natural populations. We develop a series of expressions that clarify the scaling of the time to establishment of complex adaptations with population size, mutation rate, magnitude of the selective disadvantage of intermediate-state alleles, and the complexity of the adaptation. In general, even in the face of deleterious intermediate steps, the time to establishment is minimized in populations with very large size. Under a broad range of conditions, the time to establishment also scales by no more than the square of the mutation rate, regardless of the number of sites contributing to the adaptive change, demonstrating that the emergence of complex adaptations is only weakly constrained by the independent acquisition of mutations at the underlying sites. Mutator alleles with deleterious side effects have only moderate effects on the rate of adaptation in large populations but can cause a quantum decrease in the time to establishment of some adaptive alleles in small populations, although probably not at a high enough rate to offset the increased deleterious mutation load. Transient hypermutability, whereby a subset of gamete-producing cells mutate at an elevated rate in a nonheritable manner, may also elevate the rate of adaptation, although the effect is modest and appears to result from a simple increase in the rate of transitions between intermediate states rather than from the saltational production of doublet mutations. Taken together, these results illustrate the plausibility of the relatively rapid emergence of specific complex adaptations by conventional population genetic mechanisms and provide insight into the relative incidences of various paths of allelic adaptation in organisms with different population genetic features.