Krishna was determined to recover the two provinces of Vijayanagar-Udayagiri and Kondavidu which had been captured by Prataparudra Gajapati, king of Orissa. It was a very difficult task. Both the forts had been highly fortified and were almost impregnable. His first assault to capture the fort of Udayagiri in January 1513 failed.
His forces had to widen’ the roads leading to the citadel at a great loss of men and material before they could reach the fort. It took about a year and a half to capture the fort (June 9, 1514).
His forces under the command of Saluva Timma now marched against Kondavidu, capturing many small forts on the way. Krishnadevaraya himself arrived on the scene and got wooden platforms to be constructed which were as high as the fort itself. The fort was completely blocked and ultimately captured by escalade after a fierce hand to hand fight. Among the prisoners were a queen and a prince of the Oriya king.
Bezwada was then next target. Having conquered it, Krishna took possession of Kondapalli. Gajapati who tried to intercept the advance of Krishna was defeated and had to flee to save his life.
Undeterred Gajapati made a desperate effort with the help of Shitab Khan who had 60,000 archers under him to stop Krishna near the hills of Rajahmundry. But Krishna proved more than a match for them and Shitab Khan’s men took to their heels. He captured Rajahmundry and the whole of Vengi upto Simhachalam. He erected a pillar of victory at Pottanuru and presented costly jewels to the God Varah Narasimha.
In spite of series of defeats, Gajapati was not prepared to surrender. Krishna, therefore, decided to attack Cuttack, the capital of Gajapati. It was only possible through a ‘wicked stratagem’. He arranged a fencing contest between “the son of Gajapati and one of his own men”. Gajapati prince felt it extremely humiliating to be asked to fight with a man of low birth and committed suicide.
The tragedy along with the long captivity of his queen led Gajapati to sign a treaty (A.D. 1518), according to which he gave his daughter in marriage to Krishnadevaraya. In return he got back the queen and all the territory conquered by Krishnadevaraya, north of the Krishna. Krishnadevaraya assumed the title of “gajapatisaptangharana or appropriator of (Orissa’s) seven elements of royalty”.