উল্লেখ্য, তৎকালীন শায়খুল হাদিস মাওলানা আজিজুল হকের নেতৃত্ত্বাধীন খেলাফত আন্দোলন ও আহমদ আবদুল কাদেরের নেতৃত্ত্বাধীন যুব শিবির একীভূত হয়ে খেলাফত মজলিস আত্মপ্রকাশ করে। ঢাকার ইঞ্জিনিয়র্স ইনস্টিটিউশন মিলনায়তনে এক জাতীয় সম্মেলনের মাধ্যমে এই দলটি তাদের কার্যক্রম শুরু করে।

প্রতিষ্ঠাকালে এই সংগঠনটির আমীর-এ-মজলিস ছিলেন  মাওলানা আব্দুল গাফফার, মহাসচিব ছিলেন অধ্যক্ষ মাসউদ খান, যুগ্ম মহাসচিব ছিলেন অধ্যাপক আহমদ আবদুল কাদের। কেন্দ্রীয় অভিভাবক পরিষদের চেয়ারম্যান ছিলেন শায়খুল হাদিস মাওলানা আজীজুল হক। পরবর্তীকালে আমীর-এ-মজলিস ছিলেন শায়খুল হাদিস আল্লামা আজীজুল হক। মহাসচিব ছিলেন যথাক্রমে জনাব এ আর এম আব্দুল মতিন ও মাওলানা আব্দুর রব ইউসুফী।
 
১৯৯১ খ্রিষ্টাব্দের পঞ্চম জাতীয় সংসদ নির্বাচনকে কেন্দ্র করে, ছয়টি ইসলামি দল নিয়ে এই ঐক্যফ্রন্ট গঠন করা হয়েছিল। এই দলগুলো ছিল-বাংলাদেশ খেলাফত মজলিস, খেলাফত আন্দোলন, নেজামে ইসলামী পার্টি, ইসলামী শাসনতন্ত্র আন্দোলন (বর্তমান ইসলামী আন্দোলন), জমিয়তে উলামায়ে ইসলাম ও ফরায়েজী আন্দোলন। এই জোট গঠনে মুখ্য ভূমিকা পালন করেছিলেন শায়খুল হাদিস আল্লামা আজিজুল হক, চরমোনাইর পীর মাওলানা ফজলুল করিম, মাওলানা আবদুল করিম শায়খে কৌড়িয়া, মাওলানা আশরাফ আলী ধর্মান্ডুলি, মাওলানা মুহিউদ্দিন খান ও মাওলানা আহমাদুল্লাহ আশরাফ। এই সময় শায়খুল হাদিস আল্লামা আজিজুল হক এই ঐক্যজোটের চেয়ারম্যান হিসেবে দায়িত্ব পালন করেন।

১৯৯২ খ্রিষ্টাব্দের ৬ ডিসেম্বর ভারতের অযোধ্যায় বাবরি মসজিদ ধ্বংসের প্রতিবাদে ১৯৯৩ খ্রিষ্টাব্দের ২রা জানুয়ারি আল্লামা আজিজুল হকের নেতৃত্বে খেলাফত মজলিশ ঢাকা থেকে অযোধ্যা অভিমুখে লংমার্চে বের হন। এই লংমার্চ খুলনা সীমান্তে পৌঁছলে সরকার ভারত-প্রবেশে বাধা দেওয়া হয় এবং লংমার্চের পরিসমাপ্তি ঘটে। তাঁর এই পদক্ষেপের কারণে সৌদি আরবের কিং সউদ বিশ্ববিদ্যালয়ের পরিচালনা পর্ষদের সদস্য এবং গবেষক আলেম শেখ আব্দুল ফাত্তাহ আবু গুদ্দাহ তাঁকে আলমুজাহিদুল কাবীর আখ্যা দেন। এছাড়া বাবরি মসজিদ ভাঙার পর তিনি দলীয় প্রধান হিসেবে ভারতের তৎকালীন প্রধানমন্ত্রী নরসিমা রাওকে বাংলাদেশে অবাঞ্ছিত ঘোষণা করেন এবং বিমান বন্দর ঘেরাও কর্মসূচির ডাক দেন। এই কারণে তৎকালীন বাংলাদেশ সরকার ১৯৯৩ খ্রিষ্টাব্দের ৯ এপ্রিল তাঁকে গ্রেফতার করে। পরবর্তী ৮ই মে তারিখে সরকার শায়খুল হাদিসকে মুক্ত করে দেয়।

১৯৯৬ খ্রিষ্টাব্দের সপ্তম জাতীয় সংসদ নির্বাচন-এ ঐক্যজোটের হয় এই দলটি ১টি আসন লাভ করেছিলেন মাওলানা ওবায়দুল হক। এই পদ থেকে পদত্যাগ করার প্রস্তাব দেয় জোটের শরিক দল। কিন্তু খেলাফত মজলিস এই প্রস্তাব মেনে না নিয়ে জোট থেকে বেরিয়ে যায়। কিছুদিন পরে আবারও যোগ দেয় জোটে। উল্লেখ্য, খেলাফত মজলিস বের হয়ে যাওয়ার পর ওই সময় ঐক্যজোটের চেয়ারম্যানের দায়িত্ব পালন করেন চরমোনাইয়ের প্রয়াত পীর মাওলানা সৈয়দ ফজলুল করিম। তখন মহাসচিব ছিলেন বর্তমান চেয়ারম্যান মাওলানা আব্দুল লতিফ নেজামী।

২০০৫ খ্রিষ্টাব্দের ২২শে মে ঢাকাস্থ পল্টন মোড়ের হোটেল রূপসী বাংলায় সংগঠনের তৎকালীন কেন্দ্রীয় মজলিসে শুরার সংখ্যাগরিষ্ঠ সদস্যের উপস্থিততে একটি অধিবেশন অনুষ্ঠিত হয়। এই অনুষ্ঠানে তৎকালীন নায়েব আমীর অধ্যক্ষ মাওলানা মোহাম্মদ ইসহাককে আমীরে মজলিস ও তৎকালীন নায়েবে অধ্যাপক ড. আহমদ আবদুল কাদের মহাসচিব নির্বাচিত হয়।

এই সময় অনানুষ্ঠানিকভাবেই খেলাফত মজলিস দুই ভাগ হয়ে যায়। শায়খুল হাদিস আজিজুল হকের খেলাফত মজলিশের নামকরণ করা হয় বাংলাদেশ খেলাফত মজলিস। ২০০৬ খ্রিষ্টাব্দে বাংলাদেশ খেলাফত মজলিসের আমির থাকাকালে তিনি আওয়ামী লীগের সাথে বহুল আলোচিত পাঁচ দফা চুক্তি স্বাক্ষর করেন। পরবর্তীতে অসুস্থতার কারণে তিনি খেলাফত মজলিসের আমির পদ ছেড়ে দেন এবং আওয়ামী লীগের সাথে করা সেই চুক্তিও বাতিল হয়ে যায়।

নবম জাতীয় সংসদ নির্বাচনের পূর্বে রাজনৈতিক দলের নিবন্ধন বাধ্যতামূলক করলে ২০০৮ খ্রিষ্টাব্দে সংগঠনটি খেলাফত মজলিস নামে নিবন্ধন লাভ করে। খেলাফত মজলিসের নিবন্ধন নং- ৩৮, দলীয় নির্বাচনী প্রতীক দেয়াল ঘড়ি।