Lie as in not true first appeared as a verb in the late twelfth century, while the noun didn’t show up until the end of the seventeenth century. It comes from the Old English legan/ligan and its earlier incarnation leogan, all of which had the same basic meaning we know it as. Further back in Proto Germanic, the word is leugan (the g is still present in other Germanic languages, like Dutch and of course German) and even further back, we have the Proto Indo European leugh, to tell a lie. And I promise, I’m telling the truth. : )
And we all know the word liar, which is what’s known as an agent noun, a word for a person who does something (writer from write, for example). It came into existence in the early thirteenth century, from the Old English leogere, also liar. It doesn’t seem to have a version in Proto Germanic. Instead it seems to have evolved from the West Saxon (southern England, one of the most popular dialects before the Norman invasion in 1066) leogan and the Anglian (northern England, consisting of all the dialects of Mercia and Northumbria) legan, words meaning to lie. The word seems to have appeared because people wanted something to call people who tell untruths. I guess the middle ages were as long as they could go without it.
Then we have the other kind of lie, the one that gives us all the trouble with its tenses. It showed up in the early twelfth century from the Old English licgan, meaning it was similar to the word for lie even then. It evolved from Proto Germanic as well, coming from legjanan, to lie or lay. Lay, as in lay something down, has a very similar etymology. It comes from the Old English lecgan, with an e, which evolved from the Proto Germanic lagjanan, with an a. So apparently the confusion existed even a thousand years ago.
No one ever said languages evolve in a way that makes sense. In fact, I’m pretty sure I’ve been saying the opposite ever since I started these things.
Tony Jebson’s page on the Origins of Old EnglishUniversity of Texas at San Antonio’s page on Proto Indo European language