Awal Kantor BTKLPP Palembang berada di pusat kota, terletak di Jalan Jenderal Sudirman KM. 2,5 No. 7490 Palembang. Lokasi tersebut merupakan daerah yang strategis karena dilalui sarana transportasi baik umum maupun pribadi dari dan menuju ke segala arah. BTKLPP Palembang berdiri sebagai suatu lembaga pada tahun 2000. Berdirinya BTKL Palembang atas prakarsa dari dr. Nyoman Kandun, MPH bersama stafnya Atrisman, SKM, MM yang pada saat itu menjabat sebagai Direktur Penyehatan Lingkungan Ditjen PPM-PL Depkes RI, Kepala Kanwil Departemen Kesehatan Provinsi Sumsel bersama stafnya Amar Muntaha, SKM, M.Kes
Melalui diskusi tentang hasil kegiatan dan pantauan kesehatan lingkungan di wilayah Sumatera Selatan, Kabupaten Bangka, Pangkal Pinang dan Belitung itu akhirnya dr. Nyoman Kandun, MPH dan dr. MN. Anwar, SKM sepakat memerintahkan Atrisman Nukman, SKM, MM sebagai utusan dirjen PPM-PL Depkes dan Amar Muntaha, SKM, M.Kes staf Kanwil Depkes Provinsi Sumsel untuk menyusun proposal agar di Palembang dapat berdiri BTKL yang sifatnya regional membawahi Provinsi Sumsel, Bengkulu dan Jambi serta Provinsi Lampung.
Dalam Proses pembentukan BTKL, Amar Muntaha, SKM, M.Kes menyiapkan kelengkapan data guna menyusun proposal, maka sejak 1998 BTKL Palembang sebagai embrio sudah dianggap ada dan berkantor di Kanwil Depkes Provinsi Sumsel, dan dipimpin oleh Amar Muntaha, SKM, M.Kes sebagai koordinatornya. Sejak saat itulah dalam kegiatan Direktoral jendral PPM-PL selalu diikutkan. Pada tahun yang sama Koordinator BTKL Palembang didampingi oleh dr. Mualim Rasyid, pada sat itu masih menjabat sebagai Kasubdin Penyehatan Lingkungan.
Bersama dr.Mualim Rasyid inilah Amar Muntaha, SKM, M.Kes mempresentasikan kesiapan BTKL Palembang untuk dilembagakan secara resmi oleh Menpan RI. Hasil dari pertemuan tersebut BTKL Palembang diharuskan menyiapkan gedung, personil dan peralatan terlebih dahulu, dan alhamdulillah berkat kegigihan dan kebersamaan saat itu didapatkanlah gedung eks Farmasi di Jl. Jendral Sudirman KM.2,5 No.7490. Peralatan kantor didapat dari Kanwil Depkes Provinsi Sumsel, sedangkan sumber daya manusia didapat dari Dinkes Provinsi Sumsel dan Kanwil Depkes Provinsi Sumsel.
Setelah dilakukan kelayakan dari Menpan RI maka status lembaga BTKL Palembang dapat terbentuk tahun 2000 dengan wilayah kerja Provinsi Sumatera Selatan, Bangka Belitung dan Bengkulu, sebagai PLT. Kepala Amar muntaha, SKM, M.Kes
Sejak kepemimpinan kembali di tangan Dr. Amar Muntaha, SKM, M.Kes Tahun 2012, maka beliau menganggap kantor BTKLPP Palembang saat itu tidak layak lagi untuk ditempati sebagai kantor wilayah kerja Sumatera Selatan, maka beliau mengusulkan untuk membeli tanah untuk Direktorat Jenderal PP & PL yang berada di Jl. Sultan Mahmud Badaruddin II KM.11 No.55, Alang-Alang Lebar, Palembang, Sumatera Selatan
Sejak Tahun 2013-2014 dilakukan pembangunan kantor BTKLPP Palembang sehingga nilai cerminan yang sehat dan juga ditangan beliau BTKLPP Palembang telah Terakreditasi ISO IEC 17025 - 2008 (Sekarang Terakreditasi ISO IEC 17025 - 2017
Sejak awal berdiri, BTKL PP Kelas 1 Palembang dipimpin oleh: