A design process is traditionally viewed as a sequential process model from the formulation of the problem to the synthesis of solutions. Simon (1981) regards design as a state-space search where a problem leads to the solution. To be more practical, there are many versions of solution generated during design, where each current one is an improvement over the previous one. This kind of synthesis of solutions can be viewed as an evolutionary system over time.  We propose to apply the metaphor of “exploration” to design, and further argue that evolution occurs in the problem space as well as in the solution space. Co-evolutionary design is introduced to remove the assumption of having a fixed goal (problem).  The problem is allowed to change over time. Two algorithms for co-evolution are presented. Their characteristics and differences are highlighted. The paper moves on to review the design history of the Sydney Opera House and to show how observations from this real life example confirm our co-evolutionary model.