Zoellick, the most senior US official to visit Sudan since former Secretary of State Colin Powell in July last year, arrived at el-Fashir, the capital of North Darfur state, after a visit to the interim southern capital of Rumbek.
His trip came after donor countries meeting in Oslo on Tuesday pledged 4.5 billion dollars in aid to help rebuild the devastated country.
In Rumbek, Zoellick met former rebel leader John Garang, who signed a signed a peace accord with Khartoum in January to end 21 years of civil war, Africa's longest running conflict.
The US official said Garang laid out his plans for the vast southern region, down to specifics on how he intended to use money pledged with the emphasis on infrastructure, roads, telecommunications, "the basics to build the region".
Zoellick said he also discussed with Garang, leader of Sudan People's Liberation Movement (SPLM), the feasibility of the timelines envisioned by the January peace agreement.
The pact ushered in a six-month pre-interim period during which both sides are to carry out preparations before the official six-year transitional period starts, when the south begins running its own affairs.
The war in the south erupted in 1983 when rebels led by Garang rose up against Khartoum to end Arab and Muslim domination and marginalization of the black, animist and Christian south.
Zoellick also asked for Garang's help on Darfur, particularly in dealing with tribal groups that some hope can play a role in bridging disputes between the warring parties in the region.
According to some estimates, more than 300,000 people have been killed and some two million displaced in a little over two years since the start of an uprising by rebels opposed to Darfur's marginalisation.
"He (Garang) explained that there is a fine balance there. They need to be part of the solution but at times in the history of Sudan, the government tries to manipulate tribal groups," the US official said.
After meeting government officials on Thursday, Zoellick reiterated the US administration position that hundreds of millions of dollars in aid money depended on Khartoum's readiness to comply with international demands over Darfur.
Khartoum government troops and their proxy Janjaweed militias have been widely accused of murder, rape, torture and other human rights abuses.
Darfur's main rebel group, the Sudan Liberation Movement (SLM) urged Zoellick to use his visit to Khartoum to put pressure on the government to implement UN Security Council resolutions on the conflict.
The Council passed a resolution in March demanding prosecution before the International Criminal Court of 51 suspects accused by a UN commission of war crimes in Darfur.
"We call on the US official to put pressure on the government to hand over the 51 suspects," SLM spokesman Mahjoub Hussein told AFP from London.
He also hailed Washington's efforts in bringing about a settlement to the conflict and said the SLM agreed with the American administration on the need to sustain pressure on the government in Khartoum.
Mahjoub particularly welcomed comments by US officials suggesting that the continuation of the conflict in Darfur could jeopardize assistance to the government.
"We believe that assistance should be tied to the settlement of the conflict," he said.