An automatic composition apparatus includes a processing unit. The processing unit performs a note pitch shift process, a matching-level calculating process and a melody generating process. The note pitch shift process performs pitch shift on pitches of individual note data items included in an input phrase. The matching-level calculating process calculates a matching level between a phrase including note data items subjected to the pitch shift and a designated chord progression data item, with reference to a plurality of note connection rules each of which defines a connection relation of consecutive note types, if the pitch shift is performed. The melody generating process generates a melody based on the phrase which includes the note data items subjected to the pitch shift and which is selected based on the calculated matching level.