The blast tore through the crowded Jameela market in the predominantly Shia district of Sadr City.
The Sunni jihadist group, Islamic State (IS), said it was behind the bombing and that it targeted Shia militiamen.
Meanwhile, medics say more than 20 civilians died when bombs dropped by the Iraqi air force hit a maternity and children's hospital in Falluja.
The city lies west of Baghdad and has been controlled by IS since January 2014.
The violence comes after a top American general said the US should consider embedding American troops with Iraqi forces if progress was not made in the fight against IS.
Raymond Odierno, the army's outgoing chief of staff, told reporters that such forces would have a support rather than a combat role.
Thursday's bomb attack in Sadr City was one of the deadliest in the capital since Prime Minister Haider al-Abadi took office a year ago.
In a statement posted on Twitter, IS said the truck bomb targeted Shia militiamen from the Mahdi Army and the Popular Mobilisation forces, who have been battling the jihadist group in northern and western Iraq for more than a year.
Sadr City has been the target of several bomb attacks this year claimed by IS militants, who consider Shia to be heretics.
Dozens of people have been killed in bombings across Baghdad in recent months. In May and July, large car bombs exploded outside two prominent hotels.
IS also continues to control vast swathes of territory in northern and western Iraq, but air strikes by a US-led coalition have helped Iraqi pro-government forces regain some territory since last August.
"I believe that if we find in the next several months that we're not making the progress that we have, we should probably absolutely consider embedding some soldiers with them, and see if that would make a difference," said Gen Odierno, who retires as US Army chief of staff on Friday.
"I think that's an option we should present to the president."
Gen Odierno warned that swift and more aggressive US military action would be effective only in the short-term.
"We'd probably be right back where we are today six months later," he said.
"I absolutely believe that the region has to solve this problem. The US cannot solve this problem for the region."
The US has already sent some 3,500 military trainers and advisers to Iraq.
But the Americans' aim of training 24,000 Iraqi troops has not been achieved, with only 9,000 coming forward, according to US Defence Secretary Ashton Carter.

Transport Minister Humza Yousaf said a  new charter arrangement would end the long-running row over seafarers' pay.
The RMT union had claimed some workers on board two freight boats were paid less than Â£4 an hour.
The charter change will see contracted out services return to operator Serco Northlink from next month.
The freight vessels Hellier and Hildasay have been operated by Seatruck, which is contracted to run the service by Serco Northlink.
Seatruck argued the national minimum wage was not applicable to the crew, many of whom are non-UK residents.
Serco Northlink said it had repeatedly offered to bridge the pay gap and backdate it, but Seatruck declined to accept.
Mr Yousaf said the new arrangements would come into force early next month subject to some financial and regulatory details being finalised.
He said: "I'm very pleased to see an agreement in principle now in place to end this long running issue around the freight vessels serving the Northern Isles.
"The new charter basis will allow the wage issue to be resolved. Going forward, I can confirm that all crew members will be paid at least the minimum wage."
Serco Northlink was awarded the six-year Â£243m Northern Isles contract in 2012.
It operates three ferries and two cargo boats to the Northern Isles on a route which is heavily subsidised by the Scottish government.

Penglais Farm will have a total of 1,000 rooms, but only 700 will be ready this month to welcome students.
The university said developer Balfour Beatty confirmed the remaining 300 rooms will be ready during the 2015-16 academic year.
Balfour Beatty has been asked to comment.
The unfinished rooms have not been let to students.
At least 59 people have been killed after a truck bomb exploded in north-eastern Baghdad, Iraqi officials say.
[NEXT_CONCEPT]
An agreement has been reached to ensure foreign workers on freight boats serving Orkney and Shetland are paid at least the minimum wage.
[NEXT_CONCEPT]
Hundreds of rooms at a £45m student halls development at Aberystwyth University will not be ready for the new term.