It marked the second time in less than a week that suspects have been freed in the case of the murders of 10 people, mainly shopkeepers of Turkish origin, between 2000 and 2007.
The federal prosecutor's office, based in Karlsruhe in southwestern Germany, said in a statement that it had freed two men, identified as Carsten S. and Matthias D.
The federal prosecutor said Carsten S. was still strongly suspected, together with another man, of having obtained the weapon used in nine of the killings but was unlikely to flee and had significantly helped the murder investigation.
He had also shunned contact with the far-right since at least 2001, it said.
For Matthias D., who was suspected of having supported the neo-Nazi gang on two counts, the suspicions did not justify his continued detention, it added.
The move follows the freeing on Friday of another suspect, Holger G., with the federal court of justice saying that the case against him was insufficient to justify him remaining in custody.
The suspects were arrested after it emerged in November that a neo-Nazi cell of three calling itself the National Socialist Underground was presumed to be behind the unsolved murders.
The case blew open when two of the members were found dead in an apparent suicide pact and the other, a woman identified as Beate Zschaepe, turned herself in.