Later, in a televised tribute, Mr Obama described him as one of the "most accomplished Americans to serve our democracy".
Senator Kennedy had championed issues such as education and healthcare, central to Mr Obama's first term.
In 2006, Time magazine named him as one of America's "Ten Best Senators", saying that he had "amassed a titanic record of legislation affecting the lives of virtually every man, woman and child in the country".
The BBC's Richard Lister in Washington says Senator Kennedy, known affectionately as Teddy, will be remembered as one of the most effective and popular legislators in American history.
Daniel Sandford, BBC News, Washington
President Obama was leading the tributes, saying that Senator Kennedy was the greatest US senator of our time.
But the praise was coming from right across the political divide. The Republicans were also praising him, saying that he was the kind of man that you couldn't help but like even if you disagreed with him.
That kind of praise has been echoing across the morning shows - they all broke into special coverage of the kind that is normally reserved for when former presidents die.
But of course all of the coverage has also included the controversies in Edward Kennedy's life, not least of all the death of Mary Jo Kopechne at Chappaquiddick bridge in 1969.
Our correspondent says he was also skilled at forging alliances across party lines: pushing an education initiative with President George W Bush, and immigration reform with Republican John McCain.
But he was a fierce critic of the Bush administration, in particular over Iraq and the prisoner abuse scandal.
He will also be remembered as a staunch supporter of Irish Republicanism - at one time calling for British troops to leave Northern Ireland - although he was later involved in the peace process leading to the Good Friday Agreement.
Senate Majority leader Harry Reid said the Kennedy family and the Senate had "together lost our patriarch".
This is the cause of my life... Now the issue has more meaning for me - and more urgency - than ever before, but it's always been deeply personal, because the importance of healthcare has been a recurrent lesson throughout most of my 77 years
"Edward M Kennedy, the husband, father, grandfather, brother and uncle we loved so deeply, died late Tuesday night at home in Hyannis Port (Massachusetts)," the statement said.
"We've lost the irreplaceable centre of our family and joyous light in our lives, but the inspiration of his faith, optimism, and perseverance will live on in our hearts forever."
Edward Kennedy was the only one of four brothers not to die a violent death.
His brother Joseph was killed in an air crash in World War II, and both President John F Kennedy and presidential hopeful Robert F Kennedy were assassinated in the 1960s.
He was widely expected to be the next Kennedy in the White House, but he was never able to fully overcome the scandal caused in 1969, when he drove a car off a bridge at Chappaquiddick near his home, killing his female passenger.
The incident helped derail his only presidential bid, more than a decade later.
But he remained active in politics right up until his death, famously endorsing Barack Obama for the Democratic nomination during a tight race with Hillary Clinton last year.
At his death, he was the third longest serving senator in US history.
Last week, he asked the Massachusetts governor to change state law to allow a speedy succession when his Senate seat became vacant.
Analysts suggest that Senator Kennedy feared a lengthy gap could deny Democrats a crucial vote on Mr Obama's flagship health reform.
His death comes weeks after that of his older sister, Eunice Kennedy Shriver, on 11 August.
US MEDIA REACTION TO TED KENNEDY'S DEATH
Kennedy was at the center of the most important issues facing the nation for decades, and he did much to help shape them. A defender of the poor and politically disadvantaged, he set the standard for his party on health care, education, civil rights, campaign-finance reform and labor law
He was a Rabelaisian figure in the Senate and in life, instantly recognizable by his shock of white hair, his florid, oversize face, his booming Boston brogue, his powerful but pained stride. He was a celebrity, sometimes a self-parody, a hearty friend, an implacable foe, a man of large faith and large flaws, a melancholy character who persevered, drank deeply and sang loudly. He was a Kennedy.
Seared in my memory: When I interned at the Heritage Foundation, I would pop into Mass at Saint Joseph's on the Hill. And I would almost always find myself sitting near Ted Kennedy. He's responsible for things that are deeply offensive to my conscience and diametrically opposed to the teachings of the Catholic faith, and he probably led some people astray by his example. But our faith also teaches that we are all sinners and that there is redemption. He had some incredibly good forces in his life, not least among them his sister, Eunice, who just died. I pray for the repose of his soul. R.I.P. Senator Kennedy.
Elected first in 1962, the 77-year-old Massachusetts liberal was rooted in the civil rights and Great Society battles of that decade, but his enduring strength was an ability to renew himself through his mastery of issues and the changing personalities of the Senate. Nowhere was this clearer than in Kennedy's early support of Barack Obama in 2008, when the young Illinois Democrat needed to establish himself against more veteran rivals for the White House. Kennedy not only campaigned for Obama but, at risk to his own health, opened the Democratic National Convention a year ago in Denver and returned to Washington repeatedly last winter to cast needed votes to move the new president's economic recovery agenda.
In many ways, he was the last man standing, straddling a mythic family mantle of fame and a vaunted career of political service, all the while wearing the crown of Camelot decades after its heyday...the senator's death brought to a close a storied political era - of assassinations, Jackie O, Palm Beach, Chappaquiddick - and a lifetime of both tragedy and public service.
In losing Kennedy, Obama loses a key Senate dealmaker at a crucial moment in legislative negotiations over the health care bill. Though an icon of Democratic liberalism, Kennedy was known to colleagues as a jovial pragmatist, whose many friendships with colleagues across the political and ideological spectrum made him one of the Senate's most influential players.
Bookmark with:
What are these?