Bangunan ini asalnya tidaklah sebesar yang terdapat sekarang. Bangunan ini telah ditokok tambah beberapa kali seperti yang kelihatan hari ini. Bangunan asal telah dibina dalam tahun 1935 oleh Encik Eu Tong Sen seorang pelombong dan pengusaha ladang getah yang terkenal dan kaya di Kuala Lumpur ketika itu untuk kegunaan dan kediaman keluarganya.Bangunan ini dibina di atas tanah seluas 2.6 hektar yang dahulunya adalah bekas kebun rambutan. Bangunan ini telah dibina oleh tukang-tukang yang mahir dalam selok-belok pertukangan dan pembinaan.
Mereka ini dikenali sebagai "Master Builders" dan kepandaian pertukangan yang ada pada mereka adalah hasil pengalaman praktikal mereka yang lama dalam bidang tersebut. Bangunan ini seperti juga kebanyakan bangunan persendirian ketika itu tidak menggunakan khidmat seorang arkitek yang terlatih. Pada masa itu hanya terdapat pegawai-pegawai Inggeris dalam perkhidmatan kerajaan sahaja yang terlibat dalam pembinaan bangunan-bangunan kerajaan.
Semasa meletus Perang Dunia Kedua dan sebaik saja tentera Jepun mendarat di Malaya, bangunan ini telah diambilalih oleh Pentadbiran Inggeris untuk dijadikan markas tentera mereka di Kuala Lumpur. Apabila pihak Jepun menguasai Kuala Lumpur, mereka telah mengambilalih bangunan ini dan menjadikannya juga sebagai markas tentera Jepun pula.Apabila Jepun tewas dalam tahun 1945, bangunan ini bertukar tangan semula kepada pihak berkuasa Inggeris, yang menjadikannya markas gerisen tentera mereka di Kuala Lumpur sehingga 1956. Dalam tempoh ini iaitu pada 24 Februari, 1948 telah berlangsung satu peristiwa bersejarah di bangunan ini iaitu Mesyuarat Pertama Majlis Perundangan Persekutuan bagi Persekutuan Tanah Melayu.
Semasa Persekutuan Tanah Melayu sedang giat berusaha melengkapkan diri menjelang Kemerdekaan, bangunan ini turut terlibat memainkan peranannya. Bangunan ini telah dipilih sebagai markas Tentera Persekutuan yang bertangguangjawab ke atas penubuhan dan pembangunan satu angkatan tentera bagi Persekutuan Tanah Melayu yang merdeka. Pada 15 Julai, 1956 bangunan ini dengan rasminya telah dijadikan Markas Tentera Persekutuan dan orang yang melakukan perasmian ini adalah Major Jeneral F.H Brooks seorang pegawai Inggeris yang telah dilantik sebagai Panglima Angkatan Tentera Persekutuan. Beberapa mesyuarat penting yang berkaitan dengan dasar awal ketenteraan negara telah diadakan di bangunan ini semasa ia menjadi Markas Tentera Persekutuan.