He hoped that these files would eventually be retrieved, he said at a media briefing on the intelligence services.
However, it was true that the destruction of documents had been widespread.
The directors-general of the National Intelligence Agency and the South African Secret Service had been given instructions to conduct a comprehensive audit of all documentation within the services.
Asked whether the services co-operated with the Truth and Reconciliation Commission, Nhlanhla said that if the services had information the TRC needed, they had no problem in giving it to them.
meant the TRC had access to classified documents.
While no country could do without intelligence services, which could be likened to insurance, the service was in the process of making itself fully accountable, Nhlanhla said.
Justice Minister Dullah Omar said South Africa needed an effective intelligence capacity to protect democracy and help fight crime.
The focus of the service was to ensure that intelligence existed and to co-operate with the police to ensure that intelligence was converted into evidence.
It was essential for South Africa's intelligence service to be dedicated to upholding democracy, Omar said.
NIA director-general Sizakele Sigxashe said a large number of embassies had recently opened in the country.
The service was aware of many declared foreign intelligence personnel, but there was an even bigger number who were not declared. These were under careful surveillance, he said.