Unless diagnosed early, many adult cancers remain incurable diseases. This is despite an intense global research effort to develop effective anticancer therapies, calling into question the use of rational drug design strategies in targeting complex disease states such as cancer. A fundamental challenge facing researchers and clinicians is that cancers are inherently robust biological systems, able to survive, adapt and proliferate despite the perturbations resulting from anticancer drugs. It is essential that the mechanisms underlying tumor robustness be formally studied and characterized, as without a thorough understanding of the principles of tumor robustness, strategies to overcome therapy resistance are unlikely to be found. Degeneracy describes the ability of structurally distinct system components (e.g. proteins, pathways, cells, organisms) to be conditionally interchangeable in their contribution to system traits and it has been broadly implicated in the robustness and evolvability of complex biological systems. Here we focus on one of the most important mechanisms underpinning tumor robustness and degeneracy, the cellular heterogeneity that is the hallmark of most solid tumors. Based on a combination of computational, experimental and clinical studies we argue that stochastic noise is an underlying cause of tumor heterogeneity and particularly degeneracy. Drawing from a number of recent data sets, we propose an integrative model for the evolution of therapy resistance, and discuss recent computational studies that propose new therapeutic strategies aimed at defeating the adaptable cancer phenotype.