The bodies recovered from the minibus were taken to a morgue
Eighteen were discovered in a minibus in a western district of the city populated mainly by Sunni Arabs. They appear to have been strangled or shot.
In a separate incident, two bodies were found in east Baghdad. The victims had been tied up and shot, police say.
Iraq has suffered a rise in sectarian attacks since a Shia shrine was bombed last month - but it is not clear if this was the cause in either case.
However, the dumping of bodies has previously been a sign of the violence between minority Sunni Arab and majority Shia groups.
Meanwhile gunmen in police uniforms are reported to have seized dozens of employees at a security company in the city.
The gunmen broke into the compound of the firm in the Zayouna district, Reuters news agency reported.
In other violence:
Two policemen are killed and five people hurt in a roadside bombing in central Baghdad.
Another roadside bomb targets a convoy of Iraqi Interior Minister Bayan Jabr in central Baghdad, killing two people, police and ministry sources say. The minister is not present.
At least two people are killed in a car bomb in the western town of Falluja, police say.
The US military says one of its soldiers was killed and four others wounded on Tuesday by a roadside bomb as their patrol passed in Tal Afar, north-west of Mosul.
Civilian clothes
An Iraqi security patrol found the abandoned bus on the road between Amiriyah and Khadra, two mainly Sunni districts of west Baghdad.
The men were found bound and blindfolded, officials said.
Police said the bodies had no identification papers on them. Some reports said two of the men looked like foreign Arabs.
The bodies have been taken to a morgue at the city's Yarmouk hospital.
Hospital sources told AP news agency that the deaths appeared recent and that two of the victims had been shot while the others were strangled.
The men were dressed in civilian clothes and ranged from young to middle-aged.
The bombing of the shrine at Samarra on 22 February and subsequent reprisals, in which more than 400 people have died, have sparked fears of civil war.
US ambassador to Iraq Zalmay Khalilzad said on Tuesday the country remained vulnerable to insurgents' attempts to exploit the political uncertainty caused by the bombing.
"There is a concerted effort to provoke civil war," he said.
Mr Khalilzad told the Los Angeles Times the US-led invasion in 2003 had opened "the Pandora's box" of tensions in Iraq.
US Defence Secretary Donald Rumsfeld said he did not believe a civil war was going on in Iraq, although admitted that such danger remained.
Iraq's parliament is set to sit on Sunday for the first time since the December elections.
But wrangling between Shia, Sunni Arab and Kurdish parties, particularly over the choice by the Shia-led bloc of Ibrahim Jaafari as prime minister, has cast doubt on the formation of any government of national unity.
Eighteen men, ranging in ages from young to elderly, whose bodies were found bound and blindfolded in a minibus in Baghdad, were hanged. "The medical report shows that all of them were hanged," a source at Baghdad's Yarmuk hospital said. "We found a rope round the neck of one of the victims."

A security patrol discovered the minibus just before midnight on the road between the  and Khadra districts. The victims, all men, had been handcuffed, blindfolded and either hanged or shot to death, police Lt. Maitham Abdul-Razzaq said.

Police say they have no clues to the victims' identities. The bodies were found near the Amriya district of western Baghdad — one of the city's most dangerous sections, Abdul-Razzaq said.

Official figures suggest an increase in such killings since the destruction of a major  shrine in  two weeks ago sparked reprisal attacks. Local people have accused the Shiite-led, US-backed government's police and other security forces of abducting and killing Sunni civilians.

The dumping of bodies bearing signs of torture and killed execution-style has become a feature of Iraq's violence between armed factions. 

Meanwhile, the U.S. ambassador to Iraq  warned that the country is  vulnerable to rebels’ attempts to exploit the political situation caused by the shrine attack. "There is a concerted effort to provoke civil war," he said.

Iraq's parliament is expected to sit on Sunday for the first time since the December elections.