In this paper a variable neighbourhood search (VNS) algorithm is developed that can generate musical fragments of arbitrary length consisting of a cantus firmus and a first species counterpoint melody. The objective function of the algorithm is based on a quantification of existing counterpoint rules. The VNS algorithm developed in this paper is a local search algorithm that starts from a randomly generated melody and improves it by changing one or two notes at a time. A thorough parametric analysis of the VNS reveals the significance of the algorithm’s parameters on the quality of the composed fragment, as well as their optimal settings. The VNS algorithm has been implemented in a user-friendly software environment for composition, called Optimuse. Optimuse allows a user to specify a number of characteristics such as length, key, and mode. Based on this information, Optimuse “composes” both a cantus firmus and a first species counterpoint melody. Alternatively, the user may specify a cantus firmus, and let Optimuse compose only an accompanying first species counterpoint melody.