A central challenge in evolutionary biology concerns the mechanisms by which complex adaptations arise. Such adaptations depend on the fixation of multiple, highly specific mutations, where intermediate stages of evolution seemingly provide little or no benefit. It is generally assumed that the establishment of complex adaptations is very slow in nature, as evolution of such traits demands special population genetic or environmental circumstances. However, blueprints of complex adaptations in molecular systems are pervasive, indicating that they can readily evolve. We discuss the prospects and limitations of non-adaptive scenarios, which assume multiple neutral or deleterious steps in the evolution of complex adaptations. Next, we examine how complex adaptations can evolve by natural selection in changing environment. Finally, we argue that molecular 'springboards', such as phenotypic heterogeneity and promiscuous interactions facilitate this process by providing access to new adaptive paths.