Cal Mahal eramızın 1596-cı ildə Moğol İmperiyasının zadəgan üzvlərindən olan və Narnaulun qubernatoru kimi çalışmış Şah Qulu Xan tərəfindən inşa edilmişdir. Xan Bayram xan Baharlının havadarlarından biri olmuş, Moğol məhkəməsində mühüm rəsmi şəxslərdən biri kimi çıxış etmiş və bir dəfə imperiyanın regenti olmuşdur. O, Əkbər şahın rəhbərliyi altında Moğol ordusunun ən uğurlu hərbi komandirlərindən biri olmuşdur. Xan Əkbər şahın Şimali Hindistana olan yürüşlərinə başçılıq etmişdir. İkinci Panipat döyüşündə o, Suri imperiyasının hökmdarı olan Hemunu ağır yaralamışdır. Hərbi şücaətinə görə Əkbər şah ona var-dövlət vermiş və onu Narnaulun qubernatoru təyin etmişdir.

Savadlı hərbi lider olmaqla yanaşı, Xan həm də məşhur memarlıq himayədarı hesab olunurdu. Qubernator təyin edildikdən sonra o, Narnaulda bir sıra tikinti layihəsinə start vermişdir; bu layihələrdən ən birincisi özü üçün inşa etdirdiyi məqbərə (1574-75) olmuşdur. Məqbərə "şəxsi növ" olduğu üçün Hindistanın digər ərazilərində inşa edilən layihələrdən tamamilə fərqlənirdi. Xanın layihələri haqqında məlumat müasir Moğol kitabələrində öz əksini yetərincə tapmışdır.

Məqbərinin tikintisi 15 il müddətinə başa çatdı. Bundan sonra Xan Narnaulda yeni saray inşa etdirmək qərarına gəldi; tikilən saray hal-hazırkı Cal Mahal sarayı idi. Xan adanın mərkəzində süni göl (su anbarı və ya su hövzəsi kimi də səciyyələndirilir) ətrafında sarayı inşa etdirmək əmrini verdi. Bu göl sarayın əhalisi üçün "ikinci Kovsər" (İslam cənnətində bolluq çayı) kimi nəzərdə tutulmuşdur. Xan daha sonra gölün şimal sahilində qala qapısının tikintisinə göstəriş vermişdir. Su anbarının aşağı sahilində, sarayın təməli qoyulduğiu ərazidə bənd inşa edilmişdir. Cal Mahalın və qapının tikintisi 2-3 il ərzində başa çatdırılmışdır. Saray Moğol sarayları və alaçıqları ilə eyni üslubda bəzədilmişdir. İncəsənət elementləri sarayda özünü daha çox büruzə verir. Xanın Hemu üzərində məşhur qələbəsindən bəhs edən yazılar da sarayda saxlanılır. Ərazi baxımından saray kompleksi 11 hektar ərazini əhatə edir.

Əsrlər keçdikcə sarayın su anbarı tədricən torpaqla örtülməyə başlamışdır. 20-ci əsrin sonunda torpaq parçaları tamamilə təmizlənmişdir.