Living organisms are characterized by a degree of hierarchical complexity that appears to be inaccessible to even the most complex inanimate objects. Routes and patterns of the evolution of complexity are poorly understood. We propose a general conceptual framework for emergence of complexity through competing interactions and frustrated states similar to those that yield patterns in striped glasses and cause self-organized criticality. We show that biological evolution is replete with competing interactions and frustration that, in particular, drive major transitions in evolution. The key distinction between biological and nonbiological systems seems to be the existence of long-term digital memory and phenotype-to-genotype feedback in living matter.