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