本署案前身，初為日據時代之「臺灣高雄地方法院檢察局」，設址於高雄街山下町三丁目九番地，即今高雄市鼓山區山下里山下路。民國七十八年十二月二十四日法院組織法修改，再更名為「臺灣高雄地方法院檢察署」，機關首長首席檢察官亦同時改稱檢察長。

光復後首任首席檢察官許履堂先生，因重組廳舍遭盟機轟炸，已不堪使用，乃暫借位於高雄市五福二路之高雄商業職業學校辦公；民國卅五年底再由高雄商職學校該處遠眺萬壽山，近臨仁愛河，交通便利，風景優美。嗣以司法區日趨繁榮，人口急遽增加，至七十五年間，因法院及檢察處之員額編制遽增，內部廳舍已不敷使用，乃在原地拆除重建地下二層地面六層之現代化建築，於民國七十九年完工啟用至今。

早於九十二年十二月經行政院批准籌建新地檢署，以疏解大高雄地區與日俱增之案件量，本署執行此中程計畫，歷經選地，規劃及籌建，興建工程於九十八年十月，由本署江前檢察長惠民主持之動土典禮，已有長官，地方代表，在地鄉親等均共襄盛舉與會，興建地下二層及地上十層之鋼骨鋼筋混土構造辦公大樓，工程於一百零二年順利完工，並暫由本署接管，於一百零五年九月一日成立橋頭地檢署，由本署移撥分配員額，共有相關財產設備交其接管。至此本署管轄區由原大高雄38個行政區，變更為南高雄12個行政區（鼓山區，三民區以南，包括南海上的東沙島及南沙太平島）。

為國會司法改革會議決議，打造中立，透明檢察體系，一百零七年五月二十三日總統宣布法院組織法增訂第一百一十四條之二，檢察機關名銜不冠「法院」二字，本署即於一百零七年五月二十五日更名為「臺灣高雄地方檢察署」。