But as Zuma's state visit turned from royal pomp to hard-headed politics, the two leaders largely sought to paper over differences on European Union sanctions slapped on President Robert Mugabe and his closest cohorts.
On the second day of his visit, Zuma also tried to soften remarks in which he attacked sections of the British press critical of his polygamous marriages and the scandal surrounding a child he fathered.
Zuma, who is now the regional mediator on Zimbabwe, wants the EU sanctions on Mugabe's coterie lifted.
But Brown said he wanted to see progress on the ground first, as well as the results of commissions on human rights, press freedom and governance reforms, before they are reconsidered.
"We applaud the efforts that President Zuma is making to bring stability and change to Zimbabwe," Brown said at a joint press conference after the talks at his Downing Street office.
"We however must be absolutely sure that progress is being made", he added.
Zuma warned that the sanctions issue could be exploited politically by some in Harare.
"If the Zimbabwe issue is not moving forward, certainly some people could use sanctions as an excuse," he said, noting that some ministers are subject to travel bans and others not. "There is no equality in that kind of situation."
He added: "We are agreed that we should all put our heads together to find a solution in Zimbabwe to help Zimbabweans to move forward."
Meanwhile Zuma sought to play down his earlier comments accusing some British media of having a colonialist attitude in criticising his private life.
"It was in the context of how people judge other people's cultures and who gave authority to others to judge," Zuma said.
"It's not just the British media, it is the South African media as well that has views about specific things.
"We are not necessarily trying to condemn the British."
Later, he visited the site of the London 2012 Olympic Games and then Wembley Stadium, the home of English football, where he met officials involved in England's bid to host the 2018 World Cup.
With just 98 days to go to the football World Cup in South Africa, Zuma said: "We can appreciate the hard work needed to stage such an event" and declared himself "very impressed" by Britain's Olympics preparations.
He sought to allay fears about security at South Africa's hosting of football's showpiece tournament, saying crime had been cut and visitors should not be concerned. Related article: Zuma promises safe World Cup
"The fact is we have brought down crime already. We are therefore very confident on this. And when we say we are ready now for the World Cup, we include security in that."
He added: "We are ready to protect those who come. If there are those who are sceptical or feel concern, they must know this matter has been addressed.
"They will come to South Africa safely and leave safer."
Zuma stopped short of endorsing England's bid for the 2018 tournament, but said: "I'm sure England can win."
He also visited a supermarket in Greenwich, southeast London, where he checked out South African produce, and made a low-key address to lawmakers at parliament.
The day was to finish with a banquet at the Guildhall in the City of London, the financial heart of the British capital, thrown by the Lord Mayor and Corporation of London.
Zuma started his three-day trip on Wednesday with a royal welcome from Queen Elizabeth II.
Source: AFP Global Edition