We explore a new general-purpose heuristic for finding high-quality solutions to hard optimization problems. The method, called extremal optimization, is inspired by self-organized criticality, a concept introduced to describe emergent complexity in physical systems. Extremal optimization successively replaces extremely undesirable elements of a single sub-optimal solution with new, random ones. Large fluctuations ensue that efficiently explore many local optima. With only one adjustable parameter, its performance has proved competitive with more elaborate methods, especially near phase transitions which are believed to contain the hardest instances. We use extremal optimization to elucidate the phase transition in the 3-coloring problem, and we provide independent confirmation of previously reported results for the ground-state energy of +-J spin glasses in d=3 and 4.