Reducing software complexity is key to reducing software maintenance costs. To discover complexity-reducing practices, in this paper we study the evolution of seven sizable open source programs over a long period of time. We first measure how software complexity changes as programs evolve, and identify complexity-reducing releases. We then study the changes introduced in these releases and extract evolution patterns (we call them complexity-reducing steps) that lead to reduced program complexity. Finally, we categorize these steps and discuss their effectiveness. We believe that bringing these complexity-reducing measures to light, and encouraging developers to adopt them, has the potential to improve the state of practice in software maintenance.