Kementerian Ehwal Dalam Negeri ditubuhkan pada tahun 1959 ketika Singapura mencapai kerajaan sendiri. Bertempat di Bangunan Empress Place, kementerian itu tetap berpejabat di situ sehingga 16 September 1963 apabila Singapura bergabung dengan Persekutuan Tanah Melayu (kini Malaysia) dan urusan dalaman menjadi tanggungjawab kerajaan persekutuan.

Setelah Singapura merdeka pada tarikh 9 Ogos 1965, kementerian itu kembali semula ke Place sebagai sebahagian daripada bidang kuasa Kementerian Dalam Negeri dan Pertahanan (MID). MID ditempatkan di situ selama beberapa bulan sebelum ia berpindah ke Pearl's Hill (bekas Berek Polis Hilir).

Pada tarikh 11 Ogos 1970, Kementerian Dalam Negeri dan Pertahanan dipisahkan menjadi dua kementerian, Kementerian Ehwal Dalam Negeri dan Kementerian Pertahanan. MHA masih di Pearl's Hill hingga Ogos 1977, apabila ia berpindah ke Phoenix Park di Tanglin Road.

MHA, bersama-sama dengan Ibu Pejabat Polis, berpindah ke New Phoenix Park di 28 Irrawaddy Road pada tarikh 18 Ogos 2001.