A computer program has been written which composes blues melodies to fit a given backing chord sequence. The program is comprised of an analysis stage followed by a synthesis stage. The analysis stage takes blues tunes and produces zero, first and second order Markov transition tables covering both pitches and rhythms. In order to capture the relationship between harmony and melody, a set of transition tables is produced for each chord in the analysed songs. The synthesis stage uses the output tables from analysis to generate new melodies; second order tables are used as much as possible, with fall back procedures, to first and zero order tables, to deal with zero frequency problems. Some constraints are encoded in the form of rules to control the placement of rhythmic patterns within measures, pitch values for long duration notes and pitch values for the start of new phrases. A listening experiment was conducted to determine how well the program captures the structure of blues melodies. Results showed that listeners were unable to reliably distinguish human from computer composed melodies.