Gordon Brown has been accused of "cynical pre-election politics" over his visit to British forces in Iraq.
Shadow defence secretary Liam Fox said Mr Brown preferred a photo opportunity in Basra to keeping his promise to tell MPs first about planned troop cuts.
He said the PM used the armed forces as a "political football". Sir John Major also questioned the timing of the announcement and Mr Brown's visit.
But No 10 said it was "preposterous" to suggest the PM was playing politics.
The prime minister's official spokesman said he had always planned to go to Iraq as part "of the normal process of government".
Home for Christmas
During his visit, the prime minister said that UK forces in Iraq were to be cut by 1,000 by 2008.
The Ministry of Defence has since confirmed that figure includes the 500 troops whose withdrawal was announced in July - 270 of whom are already home.
The remaining 230 and a further 500 should be home for Christmas, Mr Brown said. After that, 4,500 UK troops will remain, at the Basra Airport base.
In his first visit to Iraq since becoming prime minister, Mr Brown praised the "great courage, professionalism and bravery" of Britain's armed forces and met Iraqi PM Nouri Maliki and US General David Petraeus.
But the timing of his visit, amid mounting speculation that he is preparing to call a general election, came under fire at the Conservative Party conference.
Shadow Defence Secretary Liam Fox said MPs had been led to expect a statement on the withdrawal of troops from Basra in the House of Commons on Monday.
"It now seems that the photo opportunity has just been too great for Gordon Brown.
"And many people will see this as cynical politics, playing political football with our armed forces.
"And a lot of people, given Gordon Brown's lack of interest previously, will find this pretty cynical and unacceptable."
The Conservative former prime minister Sir John Major said he was "disappointed" Mr Brown had not made the statement to MPs first.
"It wasn't announced last week at his party conference, it was announced on the hoof in Iraq. It hasn't been announced, as it should have been, in Parliament," he said.
Asked if he agreed with Dr Fox that it was a cynical decision, Sir John said: "I think the prime minister has to show that it isn't. I am not surprised that many people think that."
Conservative leader David Cameron told the BBC he was glad more troops were coming home, but added that he "looked forward" to a Parliamentary statement spelling out the details.
"The whole country needs to hear this in Parliament - that's what our prime minister promised. That's what he should do," he said.
Asked whether Mr Brown was "playing politics" with British troops, he said the prime minister had "some questions to answer".
Meanwhile Liberal Democrat leader Sir Menzies Campbell said: "Any troop withdrawal from Iraq is welcome, but this is a cynical effort to manipulate the figures and make it look more significant than is really the case.
"In fact, only 500 more troops will be pulled out of southern Iraq, since the withdrawal of the other 500 had already been announced."
But armed forces minister Bob Ainsworth rejected the allegations, saying: "We have been saying since we got out of Basra city that we are going to be able to reduce the size of our force there. We haven't felt able to go beyond 5,000.
"We are now able to say it is not 5,000, it is 4,500. That's what the prime minister announced today.
"We are at, and have been at, 5,500 throughout the summer and we are able to go down to 4,500 - that's 1,000 less in Iraq, so what figure is he supposed to use?"
Earlier, in a speech to the Conservative conference in Blackpool, Mr Fox said everyone wanted to see British troops home from Iraq, but only when the job was done - not because of "overstretch".
He promised "a bigger Army for a safer Britain" under a Conservative government.
And he attacked Labour's treatment of the armed forces, saying its policies were "an insult to our fighting men and women".