Almost certainly yes, if you only count single bets with "underdog" long odds on single sporting outcomes - several sources have looked into this, including betting companies themselves, and found nothing that comes close.
If you allow any type of bet and aren't fussy about it being an "underdog" story (something that was added to the question after I wrote this), and you simply look for the longest odds won for a single competitor winning in a single competition, series or fixture, then arguably Frankie Dettori's "Magnificent 7" at Ascot Champion's Day in 1996 edges out Leicester with accumulated odds of 25051-1. According to the BBC, this cost the betting industry an estimated £40m, compared to Leicester's £20m, but there are several reasons why it might not be comparable.
Counting any win in a single event, league or series, by a single competitor
If we treat this as any case of one competitor winning one event, series or league, arguably, the longest odds would be jockey Frankie Dettori winning all 7 consecutive races in one day at Ascot Champion's Day, 1996, at odds of 25,051-1.
Great British Racing magazine:
The cumulative odds of these wins was 25,051-1
The Daily Telegraph newspaper also describe the odds as being 25,051-1, and the Independent tell the story of some of the lucky punters that day.
This is debatable though, since it's classed as an "accumulator" bet, and isn't a classic "underdog story" like that of Leicester (Dettori was a respected jockey riding horses whose individual odds were not especially remarkable), but it does refer to a single improbable achievement in a single sporting fixture or competition by a single sporting competitor.
Counting single bet "underdogs" only
If, however, you discount accumulators or pools and count only events treated by the bookies as single bets and given very long odds, I can't find anything close to 5,000-1.
It's hard to prove a negative, but ESPN have an analysis that concludes that Leicester have the record (written shortly before their win was confirmed):
Why Leicester City could become the biggest long shot champion in sports history
If they hold on to claim the title, it would be the biggest upset in sports history, according to William Hill press officer Joe Crilly. ... There is no previous example of an underdog the likes of Leicester City beating odds as long as 5,000-1. There have been a few 100-1 or longer shots that either shockingly came through or fell tantalizingly short.
They then list 10 examples, of which the longest odds were 1,000-1.
Sporting Life magazine also make a reasonable case that it is the most unlikely sporting event ever (if only single bets are counted):
Sport's greatest-ever upset
... the greatest sporting upset of the modern era, according to the bookmakers ... Sky Bet reporting it is the first time they have ever paid out a single outright bet at 5,000/1 ... It has also resulted in their largest-ever payout ... with the industry as a whole paying approximately £20 million.
They then go on to list seven other sporting upsets, the most unlikely of which had odds of 500-1. They also mention in passing that some of the odds listed might have been longer if there was something comparable to modern betting comparison websites forcing competition for unlikely bets.
These two articles cover sports from an American (ESPN) and European (Sporting Life) perspective. Two articles from Asian outlets Gulf News and Channel News Asia and one African sports blog also reach the same conclusion (but they aren't nearly as thorough), as does the internationally-minded Reuters.
Thanks to Jeremy French's comment, here's a BBC article that gives two more betting companies reporting it's the longest single bet odds they've ever paid out.
A quote from a representative of Coral:
"In the history of betting, certainly since it was legalised in 1961, a [single event] winner with odds of 5,000-1 has never happened ... Every bookmaker is crying out in pain"
A quote from a representative of Ladbrokes:
"This is the biggest sporting upset of all time"
