The high cost of software maintenance could potentially be greatly reduced by the automatic refactoring of object-oriented programs to increase their understandability, adaptability and extensibility. This paper describes a novel approach in providing automated refactoring support for software maintenance; the formulation of the task as a search problem in the space of alternative designs. Such a search is guided by a quality evaluation function that must accurately reflect refactoring goals. We have constructed a search-based software maintenance tool and report here the results of experimental refactoring of two Java programs, which yielded improvements in terms of the quality functions used. We also discuss the comparative merits of the three quality functions employed and the actual effect on program design that resulted from their use.