Hans-Peter Friedrich said on Thursday he had personally called the president of the Federal Office for Protection of the Constitution and told him to tell him what had happened.
The office destroyed at least four files on its informants within a neo-Nazi group which had strong links to the terror group.
Operation Rennsteig used eight informers to infiltrate the Thuringia neo-Nazi group the Thüringer Heimatschutz – from which the neo-Nazi terrorists emerged. The informant operation ran from 1997 until 2003.
The gang, which called itself the National Socialist Underground, killed nine immigrant shop owners, eight Turkish and one Greek, and a policewoman in a murder spree over nearly 13 years.
Uwe Mundlos and Uwe Böhnhardt botched a bank robbery and died in a murder-suicide, leaving their friend Beate Zschäpe to allegedly blow up their flat and then hand herself in to the police.
The emergence of the neo-Nazi terror cell as responsible for the until then seemingly unconnected murders shocked Germany – particularly as it emerged at the end of last year that the trio were known to police and intelligence services.
The Süddeutsche Zeitung newspaper reported on Thursday that crucial files from Operation Rennsteig were missing – destroyed by the Office for Protection of the Constitution, Germany's internal intelligence agency.
Four files were destroyed on November 11, 2011, the paper said – after it was realised that the time limit for keeping personal data had been breached.
This was also the same day as the connection between the neo-Nazi group and the string of murders was made.
The question now arises as to why the files were kept for so long – and why they were destroyed at exactly the time when it became important to see what had been known about the neo-Nazi trio, the paper said.
The fact that there were paid informants inside the notorious Thüringer Heimatschutz has been known for a long time, particularly with the outing of Tino Brandt, a neo-Nazi leader, as an informant.
But now that a parliamentary investigative committee is looking at who knew what and when - and how come nothing was done to stop the National Socialist Underground, details become crucial.
Jörg Zierke, head of the federal police BKA, admitted to the committee the police had failed in the case.