Five hundred and forty seconds later the craft was in orbit, ending a tense diplomatic stand-off between Russian and Kazakh authorities over the use of the former Soviet Union's main space launch facility.
The Soyuz booster rocket took off at 1637 GMT, two days later than scheduled, transporting a Progress cargo craft with food, oxygen and a navigation system to the space station's Russian-French crew.
"I am very happy that the launch was a success. It is significant in terms of whether we fulfil our planned program for the crew on board (Mir)," a visibly pleased Boris Ostroumov, deputy director of the Russian space program, said.
A Russian-Ukrainian Zenit rocket is due to be launched tomorrow after about a week's delay.
Moscow leases Baikonur, the main former Soviet space launch base, for $115 million a year. But the deal has hit trouble, with Russia failing to pay the rent.
A Russian Proton-K rocket exploded soon after launch on July 5, scattering debris over parts of Kazakhstan and raising fears that toxic fuel had contaminated the soil and water supplies.
Kazakhstan immediately halted all launches from Baikonur but, after talks, the ban was lifted Wednesday on all launches except Protons.
Soyuz and Zenit rockets use more conventional and less dangerous rocket fuel than the Protons.
Moscow wants the crew on Mir to install a navigation system as a precaution against the station spinning out of control when the three-man team leaves for earth on August 23, leaving the station unmanned.
It will take a month to install, meaning that July 16 and 18 were the last two possible launch dates for the Progress.
A Proton rocket is due to blast off on July 23, but its launch remains in doubt after last week's accident.
Yergazi Nurgaliyev, Kazakh President Nursultan Nazarbayev's representative at Baikonur, said talks were still under way to resolve the dispute over whether Proton launches could resume.
"We hope that the environment will suffer less in the future from Proton launches," he said.
The Proton is one of the main workhorses of Russia's space program and is used in commercial launches that raise desperately needed funds for Moscow.
Kazakhstan and Russia have generally enjoyed good relations since the break-up of the Soviet Union in 1991, but the Proton crash started a row which is only now starting to cool.
Russian Prime Minister Sergei Stepashin said yesterday that it was time to stop playing games with Kazakhstan, a comment welcomed by exhausted space officials in Baikonur.
Russia has said it will pay for the clean-up of the Proton wreckage and has promised to start settling $300 million in rental arrears for the cosmodrome.
Kazakhstan is demanding that the original Baikonur deal be renegotiated, giving it a commercial interest in future launches and a say over what takes off and when.