With a rallying cry to reclaim the soul of the party, Mr Gore said that Mr Dean "really is the only candidate who has been able to inspire at the grassroots level all over the country. So I am asking all of you to join in this great movement to elect Howard Dean president of the United States."
Mr Gore particularly embraced Mr Dean's anti-war stance, branding the conflict in Iraq a "catastrophic mistake".
"He had the insight and the courage to say and do the right thing," he said of Mr Dean. "Remake the Democratic party as a force for progress and good in America."
Mr Dean has been the frontrunner in the crowded Democratic race since the end of the summer. Last month he picked up the support of two of the country's largest trade unions. But despite his popularity among party activists, he has been shunned by the Democratic party establishment which believes he is too leftwing to win against President George Bush in November.
Mr Dean was clearly delighted yesterday as he stood beaming between two African statues at the National Black Theatre listening to Mr Gore's promise "to do everything I can to convince you to get behind Howard Dean".
Those in the crowd, most of whom were African-Americans, cited his opposition to the war and his desire to reverse the tax cuts as their main reasons for support.
"I'm concerned about the war and a real living wage for working people and affordable housing and I think he's committed to those things," said Pamela Green Perkins. Getting him elected "is not going to be easy", she admitted. "But if he keeps getting out there he can make it."
The surprise endorsement has buried Mr Dean's image as a maverick outsider. As Bill and Hillary Clinton have vowed not to endorse anyone, Mr Gore's name was as big a prize as a candidate could hope for. "Dean's been knighted by the ultimate insider," the Democratic consultant Dean Strother said. "It's game, set and match. It's over."
While the endorsement boosted Mr Dean's momentum and prestige, it baffled many of the other candidates. It was particularly devastating for Joseph Lieberman, whom Mr Gore chose as his vice presidential running mate in 2000.
Mr Lieberman received the news on television on Monday night. "I was caught completely off-guard," he said. Asked later whether he thought Mr Gore had betrayed him, Mr Lieberman said: "I'm not going to talk about Al Gore's sense of loyalty this morning."
But if the cheers of the small crowd at the $125 a plate breakfast-fundraiser was a sign of how far Mr Dean had come, the indifference of those sitting down to a $3.19 Egg McMuffin a block away showed how far he has to go.
No one in McDonald's on the corner of Malcolm X Boulevard knew that Mr Dean was in town. Even though he was on the front page of every newspaper, only a few knew who he was.
Mr Dean comes from one of the whitest, smallest and most rural states in America. Yet the Democratic party's electoral base is predominantly black and urban.
Despite a number of high-profile black endorsements, polls show that Mr Dean has yet to make inroads among African-Americans - without whom he will struggle to win the presidency. He did little to help matters last month after he was forced to apologise for saying he wanted to be the candidate for white Southerners with confederate flags in their pickup trucks.
While Mr Dean's camp had no idea that Mr Gore's support would come while he was in Harlem, they were delighted that it did. "He has to do a lot of reaching out," Ms Perkins said. "But I think he's making an effort. Being here today shows his desire to be accessible."
And he is learning fast, evoking the civil rights era and the war on poverty as templates for the kind of societal upheaval he has in store. "What we want is our community back and our country back," he said. "This campaign is about us going to the White House."