He sat alongside Allan Grogan, leader of Labour For Independence (LFI), at a packed fringe meeting at the Labour Party Conference in Perth and urged his party to be "tolerant of dissident voices".
The UK is a "union in decline" and requires a stronger devolution settlement than the party is currently offering with its Powers For A Purpose report, he said.
Mr McLeish's confirmation that he will vote No to independence was met with "delight" by Shadow Scottish Secretary Margaret Curran, after the latest in a series of pronouncements by the former First Minister which have been critical of the union.
Mr McLeish said: "I know nothing about LFI, but we need to be a party that is tolerant of dissident voices.
"We don't want to be known as a party that cannot brook discussion, however much it makes us uncomfortable or makes us think about things that we don't want to think about.
"And a genuine concern I have is 'let's stop hating Salmond and the SNP'.
"I don't like the fact that Salmond won in 2007 and 2011, but let's remember somebody must have voted for him and if you look at the polls just now they are not good for the Holyrood election.
"So I'm saying lets have a lot of voices and a lot of arguments."
He added: "We have got to spell out what a No vote actually means. A Yes vote is obvious.
"If it's a Yes vote on September 18 then it's back to the day jobs and we're moving in a different direction.
"But a No vote could mean many things to many people, and I think we have got to try and clarify.
"I think the party has taken a step forward in publishing the outcome of its constitutional deliberations.
"I'm slightly disappointed because I think it could have gone further."
He continued: "The union, as far as I am concerned, is in decline.
"The union doesn't have a written constitution. The union is doing nothing about England as part of the wider canvass of issues.
"It's a very vulnerable union and I believe, as part of the next six months, we should be talking about a powerful Scotland and a powerful union - but the union has to change.
"It's not Scotland that's out of step with modernity and the future of the union. I believe the union itself is causing a lot of the problems that we are facing."
Mr Grogan said it was a "great honour" to speak at a conference fringe of a party whose leader has described his movement as "a joke that you might see in the furthest fringes of the Edinburgh Fringe".
He was heckled by some delegates as he outlined his manifesto.
Mr Grogan said: "Labour For Independence consists of members, voters, supporters, former voters who felt the party had left them and not the other way around, trade unionists, councillors, former Lord Provosts and former chairs of the late Scottish Labour Party.
"We believe in the ideals and principles of the Labour Party, but we also believe that independence is the best way forward for Scotland."
Ms Curran said: "It's nice to meet Allan Grogan because I've been a member of Labour for 38 years and I've never actually met him.
"There's two great deceits being perpetrated in this debate, and we have heard them from Allan and I am a bit disappointed that we have heard them from Henry too.
"And that is somehow that this is a debate between the status quo and independence. It is absolutely not. Those of us voting no, those working in the Labour are arguing for a changed Scotland and Britain.
"The other great deceit is that somehow that the fight for equality is finished in Britain, which it most certainly isn't, but also perhaps that somehow independence will give us equality."
Mr McLeish urged voters to vote No to independence, and Yes to Labour at Westminister and Holyrood in the years ahead.
Ms Curran said: "I'm delighted that I think Henry has come out and is definitely voting No. I think that is quite interesting."
Mr McLeish replied: "That has never been in doubt."