The bodies were dug out of a mass grave in Bsaya in southern Iraq, not far from the border with Saudi Arabia.
Iraqi President Jalal Talabani, a Kurd, and Massoud Barzani, the president of Iraq's de facto autonomous Kurdistan region, led the ceremony, which began at Arbil airport.
Talabani denounced "this huge crime committed by the fascist enemy against Barzani and the Kurds.
"Tens of thousands of innocent people were buried alive in mass graves and these martyrs have become the symbol of the black regime" of Saddam.
Barzani, who took over leadership of the tribe after the 1979 death of his father, Mullah Mustafa Barzani, remembered as the founder of Kurdish nationalism, told the mourners the story of how these Kurds died.
"Eight thousand members of the Barzani tribe, aged 10 to 80, were arrested July 31st, 1983 by Republican Guard forces," Barzani said.
"After they were arrested, they first taken to Abu Ghraib prison before being brought to Bsaya, not far from the Saudi border."
Documents found after the fall of Saddam's regime indicate "that each evening, around one hundred of them were executed and thrown into mass graves," Barzani said.
"We have the names of the officials who gave the orders and those who executed them. Everything is contained in these documents," Barzani said.
Kurdish peshmerga fighters dressed in traditional baggy brown pants and with their heads wrapped in red-and-white keffiyeh scarves escorted the coffins off a plane and lined them up on the tarmac.
Widows carrying tissues and photos of their dead husbands sobbed, as even men in traditional Kurdish dress were unable to hide their emotion at the sight of so many coffins, each covered in a red-white-and-green Kurdish flag emblazoned with a shining sun.
After the ceremony, the coffins were placed in cars and driven 200 kilometers (125 miles) north to Barzan, a mountain village near the Turkish border where they were to be buried in a cemetery reserved especially for them.
Saddam's regime allegedly rounded up around 8,000 men from the tribe in northern Iraq, took them into the desert and executed them.
Saddam's trial, which is to focus on the alleged massacre of 143 Shiites from the southern town of Dujail, is set to begin Wednesday.
His regime has also been linked to the killing of around 180,000 Kurds during the Anfal campaign and the gassing of 5,000 Kurds in Halabja.