Former American President Bill Clinton has warned that Labour's biggest problem is that people take its achievements for granted.
Mr Clinton used a speech at the Labour conference to hail Tony Blair and his government as a "stunning success".
But he said his own experience in the US showed that voters did not realise that things could change quickly when power changed hands.
Mr Clinton also said Gordon Brown had a "brilliant vision for the future".
The former president left office in 2000 and saw his Democrat vice-president, Al Gore, defeated at the election.
He warned Labour delegates: "I think one of the biggest problems right now is that people take your achievements and your ideas for the future for granted.
"The reason is we have produced prosperity and social progress for so long it's easy for people to believe its just part of the landscape."
Voters either thought the achievements would have happened anyway or they believed if that if the "faces in the driving seat" changed, the new crowd would not ditch the things which worked.
Labour had to show that low unemployment, reduced inequality and a strong economy were "not an accident", he argued.
Mr Clinton pointed to a poll in The Guardian newspaper suggesting that 70% of people believed it was time for change.
"You should say: of course it is," said Mr Clinton. "It's always time for change in a great and dynamic nation."
He went on: "Do not let anyone ever present to your citizens any future choice... as change versus more of the same.
"You are the change agents in this great nation. You have been and you will be."
Mr Clinton praised the prime minister for delivering a "magnificent valedictory" speech.
"It was proud, but humble, hopeful but cautionary," he said.
"The most important thing for me - as somebody who has been there - was that it was appropriately full of gratitude, devotion and love."
Mr Clinton has been a close ally of Mr Blair while both in and out of the White House.
He said: "I want to thank Tony Blair for his leadership, for his preservation of our old trans-Atlantic alliance through quite a lot of storm as well as occasional sunshine.
"I want to thank him for his personal friendship to me through storm and sunshine.
"I want to thank Cherie and their children for their many kindnesses to Hillary and me and Chelsea and for enduring the rigours of public life.
"I want to thank Gordon Brown for his brilliant economic leadership and the entire New Labour team for their support."
Mr Clinton said he had a unique perspective as someone who had held high office and now was the spouse of a senator.
"It bothers me much more when somebody says something harsh about her than it ever did when they dumped on me on a regular basis," he said.
On international affairs, Mr Clinton also argued that economic aid could be a cheaper way of tackling terrorism than military action.
"Since we can't kill, jail or occupy all of our enemies... we also have to spend some time and money making more and more partners and fewer enemies," he said.
"It is so much cheaper to alleviate poverty, put kids in school, fight disease, build government capacity and economic capacity in a poor country than it is to fight a war."
The speech came as Cabinet ministers Alan Johnson and Hilary Benn signalled that Mr Blair could stay longer than people had expected before his conference speech - perhaps until next summer.
Later, the Labour leadership suffered a double defeat - on health reforms and council housing.