সম্রাট আওরঙ্গজেবের ৩য় পুত্র, মুঘল রাজপুত্র আজম শাহ বাংলার সুবেদার থাকাকালীন ১৬৭৮ সালে এটার নির্মাণকাজ শুরু করেন। তিনি বাংলায় ১৫ মাস ছিলেন। দুর্গের নির্মাণকাজ শেষ হবার আগেই মারাঠা বিদ্রোহ দমনের জন্য পিতা সম্রাট আওরঙ্গজেব তাকে দিল্লি ডেকে পাঠান। এসময় একটি মসজিদ ও দরবার হল নির্মাণের পর দুর্গ নির্মাণের কাজ থেমে যায়। সুবেদার শায়েস্তা খাঁ ১৬৮০ সালে পুনরায় বাংলার সুবেদার হিসেবে ঢাকায় এসে দুর্গের নির্মাণকাজ পুনরায় শুরু করেন। ১৬৮৪ সালে এখানে শায়েস্তা খাঁর কন্যা ইরান দুখত রাহমাত বানুর (পরী বিবি) মৃত্যু ঘটে। কন্যার মৃত্যুর পর শায়েস্তা খাঁ এ দুর্গটিকে অপয়া মনে করেন এবং ১৬৮৪ খ্রিষ্টাব্দে অসমাপ্ত অবস্থায় এর নির্মাণকাজ বন্ধ করে দেন।[১] লালবাগের কেল্লার তিনটি প্রধান স্থাপনার একটি হল পরী বিবির সমাধি। শায়েস্তা খাঁ ঢাকা ত্যাগ করার পর এটি এর জনপ্রিয়তা হারায়। ঢাকা থেকে মুর্শিদাবাদে রাজধানী স্থানান্তর করা হয়েছিল; এটিই ছিল প্রধান কারণ। রাজকীয় মুঘল আমল সমাপ্ত হওয়ার পর দুর্গটি পরিত্যক্ত অবস্থায় রয়ে যায়। ১৮৪৪ সালে এলাকাটি "আওরঙ্গবাদ" নাম বদলে "লালবাগ" নাম পায় এবং দুর্গটি পরিণত হয় লালবাগ দুর্গে ।[২]

 

লালবাগ কেল্লার দরবার হলের মধ্যকার জাদুঘরের প্রদর্শিত শিলালিপি।