Apabila anak Malaysia pertama, Komodor Dato’ K. Thanabalasingam dilantik untuk memimpin TLDM pada tahun 1967, semua kemudahan Tentera Laut masih berada di Singapura. Komodor Dato’ K. Thanabalasingam telah berusaha sedaya upaya untuk mewujudkan kemudahan Tentera Laut di Malaysia memandangkan TLDM telah mula membangun dengan pesat. Akhirnya pada tahun 1969, Kerajaan Malaysia telah membuat keputusan muktamad untuk membina sebuah atau lebih pangkalan TLDM yang tetap di Semenanjung Malaysia. Pada tahun 1969, negara mula menjalinkan hubungan dua hala yang rapat dengan Republik Persekutuan Jerman (FRG) dan Komodor Dato’ K. Thanabalasingam telah diarahkan oleh Perdana Menteri iaitu YAB Tun Abdul Razak yang juga Menteri Pertahanan melawat negara tersebut. Tujuan lawatan itu adalah untuk mendapatkan khidmat nasihat teknikal bagi membangunkan sebuah pangkalan Tentera Laut moden. Kementerian Pertahanan Jerman di Bonn bersedia untuk memberi bantuan tersebut dan telah melantik sebuah syarikat perunding Jerman iaitu F. H. KOCKS KG bagi mengkaji kesesuaiannya. Kajian tersebut telah siap pada Mei 1972 yang mana memutuskan pembinaan pangkalan utama Tentera Laut ditubuhkan di Lumut, Perak. Lumut dipilih sebagai lokasi Pangkalan Tentera Laut atas fakta kawasannya yang luas (lebih kurang 1,800 ekar) serta keadaan muka buminya yang baik dengan kedalaman air yang amat sesuai.

Pilihan lokasi lain yang sesuai adalah di Pelabuhan Klang. Bagaimanapun, kekurangan tanah, keadaan muka bumi yang kurang baik dan persaingan memperolehi tanah yang terhad dengan pihak berkuasa pelabuhan komersil menjadikan pilihan tersebut terpaksa diketepikan.

Kumpulan kajian yang terdiri daripada dua pegawai TLDM iaitu Kdr V. Ramachandran selaku Ketua Cawangan Operasi dan Rancangan dan Lt Kdr T.A. Scully, Pegawai Jurutera yang dilantik oleh Ketua Turus Tentera Laut telah diarahkan menyediakan Keperluan Staf Am (GSR) bagi Pangkalan Tentera Laut yang baru. GSR berkenaan diperlukan bagi menggambarkan semua keperluan dan pembangunan TLDM hingga ke tahun 1990. Pelbagai peringkat kerajaan telah mempertimbangkan kajian dan keperluan TLDM dengan telitinya dan kelulusan telah perolehi pada Ogos 1972. Reka bentuk yang lengkap disiapkan pada tahun 1973 bagi memulakan projek.

Syarikat Perunding Jerman, F. H. KOCKS KG turut membuat reka bentuk asas untuk Limbungan TLDM. Memandangkan saiz projek tersebut terlalu besar serta kompleks, mereka menyedari bahawa kerja-kerja reka bentuk yang lebih lengkap termasuk pembinaannya serta pengoperasiannya memerlukan khidmat tenaga pakar.

Bagi memenuhi keperluan tersebut, kerajaan telah melantik sebuah lagi syarikat Jerman, Thyssen Rheinstahl Technik (Thyssen) bagi menghasilkan reka bentuk yang lengkap dengan sekali gus membina limbungan TLDM. Pada tahun 1982, kontrak pembinaan diberikan kepada Syarikat Thyssen yang bakal mengkoordinasikan kerja-kerja pembinaan dengan Syarikat F. H. KOCKS KG yang mana bertanggungjawab penuh ke atas pembinaan Pangkalan TLDM kecuali limbungan. Pembinaan pangkalan Tentera Laut dibuat secara berperingkat dan kebanyakannya telah siap pada awal tahun 1980-an.