In a setback for NFL Commissioner Roger Goodell, the judge in New York vacated Goodell's decision in July to uphold Brady's four-game suspension over his alleged role in a scheme to deflate footballs used in the Patriots' January playoff victory.
The league will appeal the decision by U.S. District Judge Richard Berman, Goodell said in a statement. "While the legal phase of this process continues, we look forward to focusing on football and the opening of the regular season," the commissioner said.
An NFL spokesman said the league will not seek to put Berman's decision on hold while the appeal is pending, ensuring that Brady can take the field in the Sept. 10 home game against the Pittsburgh Steelers.
He had been banned until an Oct. 18 clash with the Indianapolis Colts, which would have cost him nearly $2 million in salary. The appeal is likely to take months to resolve.
Shortly after the decision, the Patriots posted a picture on Twitter of Brady pumping his fist in the air during a game. There was no accompanying text.
In a statement, National Football League Players Association Executive Director DeMaurice Smith called the ruling a "victory for the rule of law" and said Goodell's handling of the matter was "unfair, arbitrary and misleading."
Patriots running back LeGarrette Blount said on Twitter, "Let's goooo TB12!!! This is gonna be a fun season!!! 1st win of the year for #PatsNation."
Berman found that Goodell's ruling was plagued by "several significant legal deficiencies," including a failure to notify Brady beforehand that his alleged conduct could be punished by suspension.
"The court finds that Brady had no notice that he could receive a four-game suspension for general awareness of ball deflation by others or participation in any scheme to deflate footballs," Berman wrote.
Berman did not address the underlying allegations, including whether Brady knew of the scheme, saying it was not his role as judge to review the factual findings Goodell made as arbitrator.
The controversy has dominated sports radio, made national headlines and inspired nicknames like "Deflategate" and "Ballghazi."
Brady was suspended over the footballs used in the Patriots' 45-7 postseason victory against the Colts that sent them to the Super Bowl, where they defeated the Seattle Seahawks 28-24.
In May, Ted Wells, a lawyer the NFL hired to investigate the incident, found it was "more probable than not" that Brady was "generally aware" that two low-level Patriots employees had conspired to let air out of the footballs, which can make them easier to grip.
Wells' 243-page report, which the league called independent and cost more than $2.5 million, formed the basis for Brady's suspension.
But Berman, who seemed to call into question the report by putting the word independent in quotation marks in his ruling, said that was not enough to justify the ban and criticized Goodell for saying that Brady deserved the same penalty as a player who used steroids.
Judge overturns Tom Brady's "Deflategate" suspension The judge also said Brady's lawyers were improperly barred from cross-examining the NFL's general counsel, Jeff Pash, who helped lead the Deflategate probe, and were unfairly denied access to certain investigative notes.
In May, Patriots owner Robert Kraft said he would "reluctantly" accept rather than appeal a record $1 million fine and loss of two draft choices, including a first-round pick in 2016, imposed by the NFL against the Super Bowl champions for the team's role in the scandal.
In electing not to escalate the team's confrontation with the league over the controversy, Kraft said he disagreed with the punishment but respected Goodell and wanted to end the "rhetoric" that has swirled around the issue since January.
Amid months of recriminations and lawsuits, the stakes had grown beyond a mere four-game suspension. For the NFL and the union, the case became a test of how broadly to interpret Goodell's authority to discipline players under the players' collective bargaining agreement with the league.
For Brady, the allegations threatened his legacy as one of the NFL's all-time greats. Brady and his wife, supermodel Gisele Bundchen, are one of the country's most visible celebrity couples.
Brady was drafted with the 199th pick in the 2000 NFL draft and served as a backup for the Patriots before becoming the starter in his second season, leading the franchise to its first championship ever in 2002.
The quarterback is entering his 16th season and has played in six Super Bowls, winning four.
The NFL and the union had engaged in settlement talks for weeks with Berman, who urged them to find an acceptable solution. But a deal never emerged.
It is rare for a federal judge to overturn an arbitrator's decision, in part because the legal standard is quite stringent.
The ruling is the latest setback for Goodell, who has had arbitrators reduce or vacate punishments he has handed down in domestic abuse cases involving Ray Rice, Adrian Peterson and Greg Hardy, as well as in the "Bountygate" case in which the New Orleans Saints were accused of paying bonuses for injuring opposing team players.
The Wells report included scientific testing and analysis by a Princeton University physics professor, text message exchanges between Brady and the Patriots employees and interviews with more than 65 people, among other evidence.
In denying Brady's appeal on July 28, Goodell cited in part the quarterback's refusal to turn over his cell phone, which he destroyed while the investigation was ongoing.
Brady testified that it was his practice to destroy old cell phones to avoid leaks of personal information.
Within a day, the league and the union had exchanged lawsuits seeking to have a federal judge uphold or vacate the suspension.