One reason why it is hard to find such languages is that there isn't a sharp distinction between tonal and non-tonal languages. There also exists a number of languages said to have "accents". Norwegian and Swedish are typically claimed to have two "accents" that can be applied to words, and the physical expression of the accent difference is in terms of the F0 pattern around the stressed syllable. Historically, this developed from an ordinary stress system, which got obscured by insertion of vowels and differential treatment of affixes / clitics. It has been argued that Estonian is developing into a quasi-tonal language in connection with its Q2 / Q3 distinction in long vowels, where the most reliable cue for Q3 vowel is its distinctive falling tone.
Another related problem is that it can very difficult to convincingly reconstruct the phonetics of prosodic distinctions to the level of 5,000 or more years ago. Bantu languages are generally very regular and predictable in their development from the proto-language of about 3,000 years ago (similar to reconstruction of proto-Germanic), but the tonal system is much less regular. So while there is no doubt that the Ur-language had distinctive H and L tones, the actual correspondences and reconstructions are the messiest. The same problem with reconstructing proto tonal systems means that we can't be sure about proto-Afroasiatic. The subgroups split geographically into tonal and non-tonal languages so that it is reasonable to posit that some languages changed from tonal to non-tonal, or the opposite to the complement set. We can't make a compelling argument that proto-Afroasiatic had tone, or that it lacked tone, and standard scientific logic deems that if you posit tone in the proto-language, you have to prove its existence (the other guy doesn't have to prove its lack). Therefore, Omotic, Cushitic and Chadic must have become tonal languages, rather than losing original tone. An alternative view is "we don't know, therefore we can't say whether these languages became tonal".
There are Dutch and German dialects in Rhine River area which have developed a tonal contrast. Here is a paper that summarizes how this happened, with references to literature going beat to the 19th century. A number of Indic languages of India have developed tone, for example Dogri and Punjabi developed a tone contrast from the loss of a voicing distinction in consonants; Sylheti which is in the Bengali-Assamese subgroup similarly has developed a tonal contrast from a phonatory contrast. Influence of consonants on pitch is the most common source of the development of tone from non-tone. Opinions are somewhat mixed over whether proto-Chinese had tone, but at most, the proto-language had a marginal phonetic pitch difference that got amplified into the system of rampant tonal contrasts in the modern languages, where the conditioning factor was preceding and following consonant types.
All told, it is pretty hard to establish any language that has been tonal "forever".