A Soyuz rocket carrying six spacecraft for Globalstar Inc has lifted off from the Baikonur cosmodrome.
The US-based company is the first of the major mobile satellite phone and data services organisations to start upgrading their constellations.
The six new spacecraft were deployed by the Soyuz 100 minutes after leaving the ground at 2310 local time (1710 GMT).
A further 18 satellites will be launched over the next year to replace those that are failing.
"The way these systems work is that every time you put a satellite in space, the service improves significantly," said Tony Navarra, president of the company's global operations.
"It will take up to three months for the first six satellites to be fully put into their positions in their orbital rings or planes. We will probably have the entire constellation reconstituted, ready to be under full service by the summer of 2011," he told BBC News.
Customers using sat phones on the network have experienced an increasingly patchy service as the performance of the first generation spacecraft has degraded.
Rolled out in the late 1990s, many of these original satellites have suffered suspected radiation damage to their S-band transmitter equipment, which has limited their ability to handle two-way communications.
To compensate, the company has grown markets that rely on one-way messaging for security and safety. Its Spot services, for example, run off small devices that can be carried by a child, a backpacker or a boat, and which relay simple information back to a receiver about location and movement.
Globalstar says its $1bn replacement programme will not only restore the network to full capability but significantly enhance the services like Spot that it is able to offer in the future.
The new spacecraft have been built by the French-Italian manufacturer Thales Alenia Space (TAS). Weighing some 700kg, the satellites have a trapezoidal shape that conserves volume and allows them to be clustered on the cone-shaped dispenser Soyuz uses to deploy them in orbit.
The 24 new spacecraft will be incorporated along with eight late-stage first-generation satellites into a 32-platform constellation operating 1,414km above the Earth. This will give coverage to about 70 degrees North and South.
TAS has also been contracted by Globalstar's key competitor Iridium to build its second-generation network as well.
The Iridium system comprises 66 operational satellites. These spacecraft are not expected to begin launching until 2015.
"We have dedicated infrastructure just for building constellations," said Luigi Pasquali, CEO for Thales Alenia Space Italy.
"Our facility in Rome was established for the original, first-generation Globalstar system. In that facility we have put in place the means to build up and test satellites in series. We have stations where we park the satellite, we make something and then we move it into another bay, and so on - just like Ferrari," he told BBC News.