A computer-assisted composition tool for investigating the application of evolutionary techniques in the composition of music is presented. The nature of such an application is examined in terms of defining the possible mechanisms that provide a means for automated creativity. These mechanisms take inspiration from processes found in Darwinian-based evolution theory, genetic algorithm theory and similar aesthetically based uses of a genetic search heuristic in the visual arts. A formal model of ‘musical evolution’ is proposed, with particular emphasis placed on the ways in which a genetic algorithm can be used to effectively manipulate a variety of compositional structures within a hierarchical and generative grammar-based model of musical composition. The result is a prototype Windows MIDI application called GeNotator that allows composers to experiment with a range of musical structures by interactively ‘evolving’ them through a familiar and comprehensive graphical user interface.