They borrowed it from the people, and typically to finance wars and military spending. For example, Wikipedia suggests that the Bank of England "was set up to supply money to the King. £1.2m was raised in 12 days; half of this was used to rebuild the Navy." It's a game that everyone has to play once started; if Napoleon buys an army on credit, you'll have to raise an equal amount or face quite a problem.
As for why they've grown so large, it's because governments are quite skilled at owing large sums of money. Only a small portion of the debt comes due in full at a given moment, and they constantly reissue new debt via auction to keep it rolling. So as long as they can make coupon (interest) and the lump sum at maturity, it's not difficult to keep up. Imagine how much credit card debt you could rack up if you only ever had to pay interest.
This game will continue for as long as people lend. And there are plenty of lenders. There's pensions, mutual funds and endowments, which find public debt typically safer than stocks. And money market funds, which target 1 dollar NAV and only invest in the "safest" AAA-rated bonds to protect it. There's central banks, which can buy and sell public debt to manipulate inflation and exchange rates.
Absent some kind of UN resolution to ban lending, or perhaps a EU mandated balanced budget, these debts will likely continue to grow. You think they "collectively owe more money than can exist", but there's a lot of wealth in the world. Most nations owe less than a year's GDP. For example, the US's total wealth is in the neighborhood of 50 trillion.