Republican Sen. Norm Coleman of Minnesota says he now supports withdrawing 5,000 troops from Iraq before the end of the year, a plan proposed by Sen. John Warner of Virginia.
Coleman, who has just returned from a weekend trip to Iraq, says U.S. troops are winning the war against al Qaeda there.
Coleman told reporters the problem is that Iraqi political leaders are not moving fast enough to address power-sharing challenges.
Coleman has opposed timetables for troop withdrawals in the past, but he says pulling out several thousand troops would send a message to Iraqi leaders.
"I think the unmistakable message has to be sent to the Shia leadership that there is no blank check for Iraq," Coleman said. "That we have made gains at great cost -- cost in human lives, cost in dollars from United States taxpayers. We've made tremendous gains, but they need to be matched by the same kind of unyielding commitment to success that our troops have reflected and produced."
Coleman faces a tough re-election next year, and his Democratic opponents have been criticizing him for opposing withdrawing troops from Iraq.
Coleman said he still opposes a timetable for bringing troops out of Iraq, and reiterated his view that the U.S. will be there for a long time. But he said Warner's plan was an important symbolic step.
"We should expect from the Iraqis the same type of committment that we're getting from our men and women. And so I think the signal has to be sent, and I think this is a clear way to send a signal."
The plan by Warner, a former chairman of the Senate Armed Services Committee and Navy secretary during the Vietnam War, "doesn't solve all the problems, and it's not a solution," Coleman said.
He added that the U.S. can absorb a reduction of 5,000 troops without undermining the military effort in Iraq.
Coleman's comments come as an advance copy of a Government Accountability Office report concludes that Iraq has not met 11 of its 18 political and security goals.
Next week, Gen. David Petraeus, the top military commander in Iraq, and Ryan Crocker, the U.S. ambassador to Iraq, are scheduled to brief Congress.
While Coleman's comments on bringing home troops will put some distance between himself and the White House, he made another comment that might narrow that gap.
Coleman had opposed President Bush's plan to send more troops to Iraq, a plan known as "the surge," especially as it related to Baghdad (although he wasn't opposed to sending more troops to Anbar Province).
"I questioned the surge in the beginning," he said. "I was wrong in my assessment of what the surge could accomplish. I was wrong."
He said the surge has been a success, including in areas around Baghdad.
In Coleman's trip, he visited with both Petraeus and Crocker, as well as U.S. military officials and Iraqi government officials.
"What I saw and what I heard was as optimistic as I have heard the four times I've been in Iraq," Coleman said, noting he was able to visit Ramadi, once an insurgency stronghold but now relatively peaceful.
In a trip to Iraq last December, members of Congress weren't allowed to visit the city.
"Al-Qaida is on the run," Coleman said, which he credited to U.S. military efforts as well as support from the local community.
But he added: "Let me also say that the last four years have been riddled with bad predictions and broken promises in Iraq - and I understand that."
(The Associated Press contributed to this report)