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