The answer to this question really depends on what you mean by 'harmonies'. Assuming that you mean polyphony in a general sense, it's really hard to tell when this occurred because some of the earliest folk music still surviving today (e.g. the Cantu a tenuri of Sardinia) is in fact polyphonic - it has a bass drone, providing a tonal center for the piece, and a melody part on top. Much traditional music in India works the same way. We also know that music in ancient Greece (as well as elsewhere, such as in Egypt) must have featured rather complex forms of polyphony, but the current state of sources does not allow us to say much more. In fact, polyphony did not really enter the tradition of written music in Europe until the so-called organum style, first described about 860 CE in the Musica enchiriadis. Often this involved parallel harmonies rather than a fixed drone. Counterpoint then gradually developed from this organum style during the Middle Ages period. However, fully tonal music (thus, the 'harmonies' we are familiar with today) was a later development which occurred in stages; first, the third being acknowledged as a consonance (Late Middle Ages, starting in England), then 'modern' modal music with the Renaissance (in a way, this marks the beginning of music we can fully appreciate as modern listeners - the so-called 'extended common practice'), and finally full tonality which is credited to the Baroque period (starting about 1600).