সম্রাট আওরঙ্গজেবের ৩য় পুত্র, মুঘল রাজপুত্র আজম শাহ বাংলার সুবেদার থাকাকালীন ১৬৭৮ সালে এটার নির্মাণকাজ শুরু করেন। তিনি বাংলায় ১৫ মাস ছিলেন। দুর্গের নির্মাণকাজ শেষ হবার আগেই মারাঠা বিদ্রোহ দমনের জন্য পিতা সম্রাট আওরঙ্গজেব তাকে দিল্লি ডেকে পাঠান। এসময় একটি মসজিদ ও দরবার হল নির্মাণের পর দুর্গ নির্মাণের কাজ থেমে যায়। সুবেদার শায়েস্তা খাঁ ১৬৮০ সালে পুনরায় বাংলার সুবেদার হিসেবে ঢাকায় এসে দুর্গের নির্মাণকাজ পুনরায় শুরু করেন। ১৬৮৪ সালে এখানে শায়েস্তা খাঁর কন্যা ইরান দুখত রাহমাত বানুর (পরী বিবি) মৃত্যু ঘটে। কন্যার মৃত্যুর পর শায়েস্তা খাঁ এ দুর্গটিকে অপয়া মনে করেন এবং ১৬৮৪ খ্রিষ্টাব্দে অসমাপ্ত অবস্থায় এর নির্মাণকাজ বন্ধ করে দেন।[২] লালবাগের কেল্লার তিনটি প্রধান স্থাপনার একটি হল পরী বিবির সমাধি। শায়েস্তা খাঁ ঢাকা ত্যাগ করার পর এটি এর জনপ্রিয়তা হারায়। ঢাকা থেকে মুর্শিদাবাদে রাজধানী স্থানান্তর করা হয়েছিল; এটিই ছিল প্রধান কারণ। রাজকীয় মুঘল আমল সমাপ্ত হওয়ার পর দুর্গটি পরিত্যক্ত অবস্থায় রয়ে যায়। ১৮৪৪ সালে এলাকাটি “আওরঙ্গবাদ” নাম বদলে “লালবাগ” নাম পায় এবং দুর্গটি পরিণত হয় লালবাগ দুর্গে।[৩] সেই থেকে এখনো পর্যন্ত এটি লালবাগ কেল্লা নামে পরিচিত।
দীর্ঘ সময় যাবত এটি ধারণা করা হত যে, দুর্গটি হচ্ছে তিনটি ভবন স্থাপনার সমন্বয় (মসজিদ, পরী বিবির সমাধি ও দেওয়ান-ই-আম), সাথে দুটি বিশাল তোরণ ও আংশিক ধ্বংসপ্রাপ্ত মজবুত দুর্গ প্রাচীর। বাংলাদেশ প্রত্নতত্ত্ব অধিদপ্তরের সাম্প্রতিক উৎখননে অন্যান্য অবকাঠামোর অস্তিত্ব প্রকাশ পেয়েছে।
দক্ষিণস্থ দুর্গ প্রাচীরের দক্ষিণ-পশ্চিম কোণে একটি বিরাট বুরূজ ছিল। দক্ষিণস্থ দুর্গ প্রাচীরের উত্তরে ছিল কয়েকটি ভবন, আস্তাবল, প্রশাসনিক ভবন, এবং পশ্চিম অংশে জলাধার ও ফোয়ারা সহ একটি সুন্দর ছাদ-বাগানের ব্যবস্থা ছিল।
আবাসিক অংশটি ছিল দুর্গ প্রাচীরের পশ্চিম-পূর্বে, প্রধানত মসজিদটির দক্ষিণ-পশ্চিমে।
দক্ষিণের দুর্গ প্রাচীরে নির্দিষ্ট ব্যবধানে ৫ টি বুরুজ ছিল উচ্চতায় দুই তালার সমান, এবং পশ্চিমের দুর্গ প্রাচীরে ছিল ২ টি বুরুজ যার সবচেয়ে বড়টি ছিল দক্ষিণস্থ প্রধান প্রবেশদ্বারে।
বুরুজ গুলোর ছিল একটি ভূগর্ভস্থ সুড়ঙ্গ। কেল্লাটির কেন্দ্রীয় এলাকা দখল করে ছিল তিনটি প্রধান ভবন। পূর্বে দেওয়ান-ই-আম ও হাম্মাম খানা, পশ্চিমে মসজিদটি এবং পরী বিবির সমাধি দুটোর মাঝখানে এক লাইনে, কিন্তু সমান দূরত্বে নয়। নির্দিষ্ট ব্যবধানে কয়েকটি ফোয়ারা সহ একটি পানির নালা তিনটি ভবনকে পূর্ব থেকে পশ্চিমে ও উত্তর থেকে দক্ষিণে সংযুক্ত করেছে।
হাম্মাম খানা মূলত সুবেদারদের বাস ভবন হিসেবে ব্যবহার হত । লালবাগ কেল্লার এই দালান কে দুটি কাজে ব্যবহার করা হতঃ হাম্মাম খানা (বাস ভবন হিসেবে), দেওয়ানে আম (বিচারালয় হিসেবে)। এই দালানের নিচ তালা ছিল বাস ভবন তথা হাম্মাম খানা আর উপরের তলা ছিল আদালত বা দেওয়ানে আম। শায়েস্তা খাঁ এই ভবনে বাস করতেন এবং এটাই ছিল তার আদালত। এখান থেকে তিনি সমস্ত বিচারকার্য পরিচালনা করতেন ।
লালবাগ কেল্লার তিনটি স্থাপনার মধ্যে অন্যতম এটি। এখানে পরী বিবি সমাহিত আছেন। শায়েস্তা খান তার কন্যার স্মরণে এই মনমুগ্ধকর মাজারটি নির্মাণ করেন। লালবাগ কেল্লার তিনটি বিশাল দরজার মধ্যে বর্তমানে জনসাধারণের জন্যে উন্মুক্ত । এই দরজা দিয়ে ঢুকলে বরাবর সোজা চোখে পড়ে পরী বিবির সমাধি। আসলে “লালবাগ কেল্লা” বলতে যেই ছবিটি বেশি পরিচিত সেটি মূলত পরী বিবির সমাধির ছবি। পরী বিবি যার অন্য নাম ইরান দুখত রহমত বানু ছিলেন সুবাহ বাংলার মুঘল সুবেদারশায়েস্তা খানের কন্যা। মুঘল সম্রাট আওরঙ্গজেবের পুত্র শাহজাদা মুহাম্মদ আজমের সাথে ১৬৬৮ সালের ৩ মে পরী বিবির বিয়ে হয়। ১৬৮৪ সালে পরী বিবির অকালমৃত্যুর পর তাকে নির্মাণাধীন লালবাগ কেল্লার অভ্যন্তরে সমাহিত করা হয়। তার সমাধীস্থলকে চিহ্নিত করে পরী বিবির মাজার নির্মিত হয়। পরী বিবির মাজারের স্থাপনাটি চতুষ্কোণ। মার্বেল পাথর, কষ্টি পাথর ও বিভিন্ন রং এর ফুল-পাতা সুশোভিত চাকচিক্যময় টালির সাহায্যে অভ্যন্তরীণ নয়টি কক্ষ অলংকৃত করা হয়েছিল। মাঝের একটি ঘরে পরী বিবির সমাধিস্থল এবং এই ঘরটি ঘিরে আটটি ঘর আছে। স্থাপনাটির ছাদ করবেল পদ্ধতিতে কষ্টি পাথরে তৈরি এবং চারকোণে চারটি অষ্টকোণ মিনার ও মাঝে একটি অষ্টকোণ গম্বুজ আছে। মূল সমাধিসৌধের কেন্দ্রীয় কক্ষের উপরের এই গম্বুজটি একসময়ে স্বর্ণখচিত ছিল, পরবর্তীতে পিতলের/তামার পাত দিয়ে পুরো গম্বুজটিকে মুড়িয়ে দেওয়া হয়েছে। স্থাপনাটির অভ্যন্তর ভাগ সাদা মার্বেল পাথর দিয়ে আচ্ছাদিত ছিল।[৪][৫] ২০.২ মিটার বর্গাকৃতির এই সমাধিটি ১৬৮৮ খ্রিষ্টাব্দের পূর্বে নির্মিত। তবে বিশেষজ্ঞদের অভিমত বর্তমানে এখানে পরি বিবির মরদেহ নেই বলে।
সম্রাট আওরঙ্গজেবের তৃতীয় পুত্র শাহজাদা আজম বাংলার সুবাদার থাকাকালীন তিন গম্বুজওয়ালা দুর্গ মসজিদ এই মসজিদ নির্মাণ করেছিলেন ১৬৭৮-৭৯ খ্রিষ্টাব্দে। আয়তাকারে (১৯.১৯ মি: × ৯.৮৪ মি) নির্মিত তিন গম্বুজ বিশিষ্ট মসজিদটি এদেশের প্রচলিত মুঘল মসজিদের একটি আদর্শ উদাহরণ। বর্তমানেও মসজিদটি মুসল্লিদের নামাজের জন্য ব্যবহৃত হয়ে আসছে।