Qwest Communications has earned a multi-billion dollar payout for its long-shot bet to become one of the primary providers of telecommunications services to the U.S. federal government.

Qwest was one of three carriers selected on Thursday for Networx Universal, a 10-year federal government program that is the largest network services deal in the world.

The other Networx Universal winners are AT&T and Verizon Business, both of whom have won predecessor contracts with the U.S. federal government. Networx Universal is the first win of this magnitude for Qwest.

Winning Networx Universal is “validation by what I might argue is a pretty discriminating customer that Qwest is a Tier-1 national communications company,” says Tom Richards, executive vice president, Qwest Business Markets Group.

Richards says winning Networx Universal is a key milestone for the company, which has suffered accounting scandals, financial disappointments and failed merger attempts in recent years.

“It gives us a significant opportunity from a revenue generation standpoint,” Richards says. “We now have a hunting license for 135 to 140 agencies. Even though we’re a substantial supplier to the federal government today, this [contract] clearly expands our horizons.”

Networx Universal will provide domestic and international voice, data, video and wireless services to federal agencies for the next decade.

Qwest beat out incumbent Sprint Nextel, which has served the U.S. federal market for 18 years.

“Qwest was the dark horse candidate,” says Ray Bjorklund, senior vice president with FedSources, a market research firm. “This is a big win for Qwest.”

Qwest already supports several federal agencies including the Treasury and Justice Departments, the U.S. Postal Service, the Energy Department and the Defense Information Systems Agency. The Networx Universal award allows Qwest to go after billions of dollars in federal telecommunications services that will be up for grabs over the next decade.

The General Services Administration announced the Networx Universal winners at a press conference in Washington, D.C. on Thursday.

John Johnson, Assistant Commissioner for Integrated Technology Services with the GSA’s Federal Acquisition Service, says all three Networx Universal winners “met the goals and objectives of the government.”