Historis cikal bakal keberadaan asrama haji di Indonesia, diawali sejak dimulainya pemberangkatan jamaah haji Indonesia ke tanah suci dengan menggunakan kapal laut. Tempo dulu hanya dikenal beberapa asrama haji, seperti asrama haji Jakarta, Semarang, Surabaya, Balikpapan, dan lainnya. Kewajiban masuk asrama haji mulai diterapkan tahun 1970, berbarengan turunnya aturan dari pemerintah Arab Saudi yang mengharuskan semua jamaah haji Indonesia dikarantina selama lima hari, sebelum pemberangkatan dan lima hari setelah tiba kembali di tanah air (Indonesia). Kewajiban karantina selam lima hari dimaksud, berlaku sampai dengan tahun 1972. Ketentuan lima hari sebelum pemberangkatan dan lima hari setelah tiba di tanah air, pada tahun 1973 berubah menjadi tiga hari sebelum pemberangkatan dan setelah tiba di Indonesia.

Kondisi tahun 1973 Pemerintah Indonesia belum memiliki asrama haji, untuk mengkarantina jamaah hajinya sebagaimana ketentuan Pemerintah Arab Saudi. Upaya memenuhi ketentuan dimaksud, pemerintah Indonesia menerapkan pola sewa tempat pada wisma swasta. Pola sewa tempat sangat tidak memuaskan pemerintah, baik dari aspek fasilitas yang disediakan tidak memenuhi kebutuhan jamaah maupun biaya sewa yang sangat tidak relevan membuat pemerintah harus merencanakan pembangunan asrama haji.

Rencana pembangunan asrama haji mulai digagas pada tahun 1974 oleh Direktur Jenderal Urusan Haji Prof. KH. Farid Ma’ruf. Realisasi pelaksanaan pembangunan asrama haji pertama, adalah Asrama Haji Pondok Gede Jakarta pada masa Menteri Agama dijabat oleh Alamsyah Ratu Perwiranegara dan Direktur Haji dijabat Burhani Tjokrohandoko. Pasca pembangunan asrama haji pondok gede, jamaah haji yang berangkat menggunakan jasa penerbangan meningkat tiga kali lipat. Melihat animo masyarakat sangat tinggi, pemerintah mengembangkan pelaksanaan pembangunan asrama haji di beberapa wilayah Jakarta, Surabaya, Makassar dan Medan.

Asrama Haji Medan dibangun atas dasar peningkatan jumlah jamaah calon haji di Pulau Sumatera, tercatat pada tahun 1979/1980 jamaah haji yang diberangkatkan dari Asrama Haji Medan sebanyak 4.463 orang, terdiri dari pria 1.933 orang dan wanita 2.530 50 orang tergabung dalam 15 kloter, jamaah calon haji ini terbagi dari berbagai daerah mulai dari Aceh yang berjumlah 752 orang, Sumut 1.729 orang, Sumbar 1.157 orang, Riau 617 orang, ABRI 86 orang, setoran khusus sumatera 117 orang dan petugas 5 orang. Menanggapi kondisi tersebut, pada tahun 1977 diadakan pengajuan lokasi pertapakan pembangunan asrama haji Medan yang ditinjau langsung oleh pejabat kemenag yaitu di desa Pangkalan Masyhur Titi Kuning, Kecamatan Medan Johor dengan kondisi tanah rawa, baru pada tahun 1978 pihak kemenag berhasil melakukan pembebasan lahan dengan ukuran 30.188 m².

Gedung pertama yang dibangun adalah gedung Johor Medan (sekarang gedung Raudhah) yang berfungsi sebagai kantor Badan Pengelola Asrama Haji (BPAH) dengan luas 300m² dengan kapasitas 17 orang, pada tahun 1979 asrama penginapan petugas dan pembantu dan asrama penginapan jamaah haji seluas 1.114m² dengan kapasitas 278 orang dibangun, kemudian ditahun yang sama masjid dengan luas 300m² berkapasitas 250 orang juga dibangun. Pada tahun 1980/1981 dibangun asrama bertingkat dua seluas 1.685m² berkapasitas 440 orang (sekarang disebut gedung Arafah) dan juga pada tahun yang sama dibangun Aula I (Gedung Madinatul Hujjaj) seluas 1.500m². pada musim haji 1982 kedua gedung ini sudah dapat digunakan. Hingga sekarang Asrama Haji Medan mengalami revitalisasi di tahun 2014 dan diresmikan pada tahun 2016 oleh Menteri Agama. Asrama Hji Medan disebut memiliki standar setara dengan hotel berbintang 3. Pelayanan para jamaah pada asrama haji ini dipusatkan pada sebuah gedung bertingkat 5 dengan tiap lantainya memiliki berbagai fasilitas yang berbeda-beda.