This medieval fort is situated at 20°29′1.32″N 85°52′3.36″E / 20.4837000°N 85.8676000°E / 20.4837000; 85.8676000, about 8 km from the center of the Cuttack, at the apex of a delta formed by the river Mahanadi in the north and its distributary, the Kathajodi in the south, and is located at 14.62 metres above sea level.

The Barabati was built in 987 CE by the Somavamshi dynasty lineage ruler Maharaja Markata Keshari while building a stone embankment to protect Cuttack which was known as Kataka at that time.

Seeing this, the king was very much surprised; on an auspicious day, he laid the foundation of construction of the fort and this village was named Barabati Cuttack.

To the east of the mound, there is the Shahi Mosque while in the west of the tank lies the mazar (tomb) of Hazrat Ali Bukhari.

In 1989, excavations were carried out by Archaeological Survey of India to ascertain the cultural horizon of the historic fort and the work is still in progress.

Excavation by Archaeological survey of India on December 1, 1989, revealed evidence of a palace, a square structure built up of Khondalite stone.

Trenches dug on the eastern side of the structure revealed 32 pillars built of literate blocks roughly square but varying in size.

Archaeological surveys reveal that the Fort was roughly rectangular in structure having an area of over 102 acres (0.41 km2), and it was surrounded on all sides by a wall of laterite and sandstones.

During the 1989 excavation, the central mound area of the fort revealed the remains of a palace, a pavilion and foundation blocks made of rhodolite.

The pottery finds comprised storage jars, spouted vessels, lamps, knobbed lids, miniature pots, dishes and bowls, the final portion of a hukkah and pieces of Chinese porcelain.