The fort at Bathinda is possibly the oldest in Punjab, going back as far as the early Christian era. Intended as a safeguard against invasion, the Qila Mubarak resembles a great big schooner soaring over dusty plains. It was ruled by successive dynasties, each of which, including Baba Ala Singh of Patiala, has left an indelible mark on its construction. The Qila Mubarak is associated with a celebrated historical romance. Malik Ikhtiar-ud-din Altunia, the 13th century governor of Bathinda rebelled against Empress Razia Sultan, one of the post powerful rulers of the Delhi Sultanate, and imprisoned her here. They are said to have fallen in love during her captivity and gotten married there after.