District Court Judge J Frederick Motz said he was not convinced the deal would produce a fair conclusion to the case. The proposal would have funnelled about $1bn (£690m)-worth of computers, software and support to the poorest schools in the US.
Motz wrote: "I cannot presently determine the adequacy of the proposed settlement because the record has not been sufficiently developed on the question of the underlying value of the class claims".
Microsoft expressed disappointment in the decision, but said it was "confident" that it would ultimately prevail in the litigation. "Microsoft is always open to looking for reasonable ways to resolve litigation. We will review the court's opinion and at the same time move forward with the next steps in the litigation," said Tom Burt, deputy general counsel for Microsoft.
One lawyer representing some of the private plaintiffs in favour of the settlement offered a similar response.
"We are disappointed that the settlement did not receive preliminary approval. We believe it would have done a lot of good," said Dan Small, an attorney representing individual and corporate plaintiffs in the case. "We are prepared now to litigate the case against Microsoft."
Talks to settle disagreements surrounding the proposed settlement failed to produce results by the 10 January deadline.
"I wouldn't say that (the mediation) failed; it never really got started," said Steven Benz, an attorney with Kellogg, Huber, Hansen, Todd & Evans. "Dealing with Microsoft is a unique experience."
Apple had criticised the proposed deal, saying that it would help solidify Microsoft's monopoly in the desktop operating system market by extending it to the education sector. Linux software maker Red Hat was also a vocal opponent to the deal.
Red Hat proposed its own "settlement", which involved distributing its open source operating system instead of Microsoft's Windows.