建立沿革:
義善堂主祀義善姑,據廟誌記載,義善姑乃抗日巾幗英雄,相傳日人佔領臺灣時,因日軍不守軍紀,四處欺壓百姓,於是義善姑起而抗日,奮勇於夜間偷襲,不料反被日本士兵追趕到今日俗稱的「荖葉坑」之地時,因寡不敵眾而被日軍追殺成仁。
因當地人畏懼日軍暴行,不敢將義善姑屍體領回,等到日軍離開後,才把義善姑就地於今尖山埤水庫附近埋葬。至此之後此地經常發生了一些神奇事蹟,所以村民便在此處山路邊,蓋了一座簡單的小廟宇,當時人稱「崎腳公」。
大正15年(1926),鹽水製糖株式會社新營製糖株式會社(今日的新營糖廠),興建尖山埤蓄水池時,一位日本清負組頭太田英一,負責掘砌土方,而這座小廟剛好就在這附近,這個工程施工所用的輕便車,每天有二十多次出軌,或發生其他的事故,導致工程無法順利的進行。當時有一位本省人向日本組頭建議此廟若無法移建他處,則工程便無法進行。組頭聽了,於是在昭和12年(1937年)將小廟遷至現今廟址,工程也得以順利施工。
戰後,廟宇又於民國63年(1974)擴建,並由新吉庄張水源、潘連亭,二重溪的王慶雲等人士創起管理,早晚由施振坤奉香獻茶果,白天由新吉庄的張蔡頭義務管理,並以善姑娘愛國義勇之精神改稱義善堂義善姑。