Warships from India, Russia, NATO and the U.S. are also cruising the Somali waters that have been plagued by pirate attacks in recent months.
The Chinese ships left early Friday afternoon from a base on the southern island province of Hainan, the official Xinhua News Agency and CCTV reported. China announced it was joining the anti-piracy mission Tuesday after the U.N. Security Council authorized nations to conduct land and air attacks on pirate bases.
Pirates have made an estimated $30 million hijacking ships for ransom this year, seizing more than 40 vessels off Somalia's 1,880-mile (3,000-kilometer) coastline.
Deploying ships to the Gulf of Aden marks a significant step in the evolution of China's navy, according to a report by Stratfor, an Austin, Texas-based intelligence company. The mission will be complicated, offering vital on-the-job training in refueling, resupply and repairs far from home as well as patrolling for pirates, Stratfor said.
"In the event of an accident or a run-in with pirates," Stratfor said, "would a Chinese vessel carry out repairs at sea, head to a nearby port, perhaps in Pakistan, or return to China?"
Stratfor also noted the waters will be awash with naval ships from around the world, making it essential for China to maintain effective communication with the vessels.
The Chinese "will very likely monitor the way NATO and especially U.S. warships communicate with each other and with their shipborne helicopters," the report said.
China's willingness to send ships so far from home is also the latest example of the growing power and confidence of the country's navy. In recent years, the military has been loading up on warships, planes, missiles and other weapons
- a beef-up that has worried its neighbors and the U.S.
Those most concerned include the Japanese and South Koreans, who have long-standing disputes about territorial waters that occasionally flare up. China has also been locked in an uneasy stand off with the Philippines, Vietnam and other Southeast Asian nations over the ownership of the potentially oil-rich Spratly Islands in the South China Sea.
Denny Roy, a senior fellow at the East-West Center in Hawaii, said countries in the region will view China's mission off Somalia differently.
"For Japan and some in South Korea, this is another step in the unwelcome growth of the Chinese navy as a capable blue-water force, which has only downsides for Tokyo and Seoul," said Roy, an expert on China's military.
But he said most Southeast Asian countries may see China's involvement in the anti-piracy campaign as a positive thing. It would mean that China was using its greater military might for constructive purposes, rather than challenging the current international order.