After dealing with the Mudigonda Chalukyas, Ganapatideva turned to coastal Andhra like his father before him. The Kakatiyas launched a military campaign into the Krishna delta region in 1201, with an army commanded by Malyala Chaunda. The Krishna delta region was ruled by the Ayya chief Pinna Chodi from his island-fortress at Divi. After a difficult siege, Malyala Chaunda was able to capture the fortress, earning the title [i]dvipi-lumtaka[/i]. King Ganapatideva was quite impressed by the abilities of Jayapa, the son of Pinna Chodi, and so recruited him into the royal service. In addition, the Ayya family was allowed to continue to rule the Krishna delta as vassals of the Kakatiyas.
Pinna Chodi was most likely a vassal of the Velanati Choda king Prithvisvara before being subjugated by the Kakatiyas, so attacking Pinna Chodi also meant war with the Velanati Chodas. Sometime after Malyala Chaunda's campaign, King Prithvisvara marched south to the Krishna region. However, he was met by a coalition of forces who were opposed to the Velanati Chodas, including the Kakatiyas, Prince Tikka Bhupala of Nellore, and Mahamandalesvara Ballaya of Kammanadu. The Velanati Choda army was destroyed by the allied forces, and King Prithvisvara was killed. Subsequently, both Ganapatideva and Tikka Bhupala took the title [i]Prithvisvara-shirah-kanduka-krida-vinoda[/i], i.e. "one who played ball with the head of Prithvisvara." The last known record of Prithvisvara was in 1206, while the earliest known record of Ganaptideva in Velanadu (roughly the region between the Krishna and Penner rivers) is in 1209. Thus, it seems that Velanadu was annexed by the Kakatiyas sometime between 1206 and 1209. In 1213, Ganapatideva appointed Jaya-senapati as governor of the province.
Shortly after the Kakatiya conquest of Velanadu, Ganapatideva also intervened in Nellore on behalf of his new ally, Tikka Bhupala. Until c.1208, Nellore was ruled by the brothers Nallasiddhi and Tammusiddhi, who were nominally subject to Kulottunga Chola III. However, Tikka Bhupala considered himself to be the rightful ruler of Nellore, as he was the son of the previous king Manumasiddhi. Ganapatideva thus advanced on Nellore and installed Tikka Bhulapa as a subordinate ruler. Jayapa, the son of Pinna Chodi, was appointed as the viceroy over this southern region.
Sometime after the Nellore expedition and before 1213, the Kakatiyas also launched an invasion of Kalinga. An army commanded by Rajanayaka and Induluri Soma-mantri was sent north of the Godavari river, and managed to penetrate as far as Aska in the modern Ganjam district. However, the Kakatiyas were not able to hold on to this territory. The Eastern Ganga king Ananga Bhima III, who ascended the throne in 1211, succeeded in driving back the Kakatiyas, and was even able to cross the Godavari river into Vengi.
Following the Kalinga expedition, a state of uneasy peace seems to have prevailed between the Kakatiyas and Eastern Gangas for about two decades. The territory north of the Godavari was under Eastern Ganga rule during this time, as evidenced by their inscriptions at Draksharama (the last such inscription being dated to 1233). However, the Gangas also failed to make any headway into the Vengi region, located south of the Godavari river. The most important local potentate of Vengi during this time was Mahamandalesvara Kolani Kesavadeva (1192-1228), who ruled the Kolanu region in modern-day West Godavari district. The region of Kolanu was eventually conquered by Induluri Soma-mantri, who was henceforth called Kolani Soma. The Draksharama inscription of the Kakatiya general Mallala Hemadi Reddi, dated to 1237, also indicates that the territory immediately north of the Godavari delta came under Kakatiya control in the 1230s.
In the south, King Ganapatideva's ally in Nellore, Tikka Bhupala, died in 1248. However, the succession of Tikka Bhupala by his son, Manumasiddhi II, was disputed by Vijayaganda Gopala, a Choda pretender. Vijayanaganda Gopala rose in rebellion and seized the southern part of the Nellore kingdom, including the modern-day Thiruvallur and Vellore districts of Tamil Nadu. Meanwhile, the ministers Bayyana and Tikkana also rose in revolt against Manumasiddhi II, and drove him out of Nellore. Manumasiddhi II thus appealed to King Ganapatideva for assistance, who sent an army south under Samanta Bhoja. The Kakatiya army recaptured Nellore, put Bayyana and Tikkana to death, and re-installed Manumasiddhi II as ruler. Samanta Bhoja then proceeded further south, where he decisively defeated Vijayaganda Gopala at Palaiyaru in the modern-day Thanjavur district. The city of Kanchi was captured by the Kakatiya army in 1250.
The final military action of Ganapatideva was a conflict with the Pandyas of southern Tamil Nadu. Jatavarman Sundara Pandyan, who ascended the throne in 1251, conquered Kanchi and Nellore in the late 1250s. He then sent an army under the Kadava chief Kopperunjingan to invade Velanadu. King Ganapatideva was able to repulse this incursion, but he was unable to recapture Nellore or Kanchi. Manumasiddhi II, the Kakatiyas' ally in Nellore, was killed by the Pandya army at the Battle of Muttukuru in 1263. The Kakatiyas would not reassert their authority in this southern region until the early 1300s.