A piece of popular music is usually defined as a combination of vocal melody and instrumental accompaniment. People often start with the melody part when they are trying to compose or reproduce a piece of popular music. However, creating appropriate instrumental accompaniment part for a melody line can be a difficult task for non-musicians. Automation of accompaniment generation for vocal melodies thus can be very useful for those who are interested in singing for fun. Therefore, a computer software system which is capable of generating harmonic accompaniment for a given vocal melody input has been presented in this thesis. This automatic accompaniment system uses a Hidden Markov Model to assign chord to a given part of melody based on the knowledge learnt from a bank of vocal tracks of popular music. Comparing with other similar systems, our system features a high resolution key estimation algorithm which is helpful to adjust the generated accompaniment to the input vocal. Moreover, we designed a structure analysis subsystem to extract the repetition and structure boundaries from the melody. These boundaries are passed to the chord assignment and style player subsystems in order to generate more dynamic and organized accompaniment. Finally, prototype applications are discussed and the entire system is evaluated.