There is a theory about tonogenesis for the Chinese language, thus Chinese had once a more complex syllable-structure and no tones. In the course of time, the syllable structure became less complex and tones emerged to compensate this loss.
I am not sure about the other way, the loss of tones. For instance, I read a short notion about old Greek being a language that features pitch accent, if am right pitch accent is the alteration of the frequency, is this similar to tone?
It is generally assumed that proto-Indo-European had a pitch accent, which survives in the notation of Classical Greek and of Vedic, but which has disappeared in Modern Greek as well as in Classical Sanskrit and the Middle and New Indo-Aryan languages. The IE pitch accent survives at least partially in Lithuanian.
Korean was a tonal langauge until the 16th Century. In fact, even today the Gyeongsang dialect still uses tones.
From my ancedotal experience, remanents of tone are still visible in the "standard" Seoul dialect as well (mostly related to length of articulation), but they aren't ubiquitous among speakers and are not taught to Korean Second Langauge learners.
Proto-Bantu and Proto-Niger-Congo were tonal, and a number of daughter languages have become non-tonal (examples: Kutu, Pogolo, Mbunga, Zaramo, Swahili, in East Africa; most North Atlantic languages; the Gur language Koromfe; the Mande language Bis(s)a).
Older stages of Japanese held much richer inventories of tonal contrast than the modern "standard" Tokyo dialect, which is rather restricted in its lexical tonal contrasts. And some other modern dialects have lost lexical tonal contrasts altogether.
This Wikipedia article on Japanese pitch accent provides a map that shows areas where such non-tonal dialects are spoken.
