The bid was based on his application for amnesty before the Truth and Reconciliation Commission earlier in the day.
"We believe he should not be extradited before the commission has heard his amnesty application," a spokesman for Veenendaal, Pieter Aucamp, said.
The case was postponed to Wednesday for a date to be determined.
In terms of the extradition order Veenendaal had to give himself up to police by 1pm on Wednesday.
Aucamp said there was no danger of him being extradited while the court hearing was ongoing.
"There will be more clarity on the case by about noon tomorrow (Wednesday)," he added.
An extradition order was served on Veenendaal on Monday in connection with a 1989 bomb attack on United Nations offices in Outjo in northern Namibia, in which one person died.
Interpol director Dave Bruce said charges against Veenendaal included murder, theft and several transgressions of Namibian arms and ammunitions legislation.
Namibia applied for his extradition in 1990.
Bruce said Veenendaal appeared before the Johannesburg Magistrate's Court on April 30, 1992 and was found extraditable by the judge.
He embarked on a 77-day hunger strike while awaiting former Justice Minister Kobie Coetsee's decision on the matter, and was granted bail in November of that year.
"It took the Justice Ministry up to now to decide to extradite Mr Veenendaal," Bruce said.
In terms of the extradition order, Veenendaal had to hand himself over to police before 1pm on Wednesday, after which he would be detained until the Namibian authorities arrived to fetch him.
Should he not comply a warrant for his arrest would be issued.
Veenendaal on Tuesday vowed to fight the extradition order tooth and nail.
"The case has been left alone for over four years. I have since started a new life. This is ridiculous," he said.
A Ministry of Justice spokeswoman said no extradition agreement existed between South Africa and Namibia.
"It is, however, possible to extradite a person with the permission of the president," she said.