建立沿革:
雍正2年（1724）漳州陳姓先民自中國原鄉渡海來臺，為求航行平安，至漳州府金浦縣龍頭堡蜈蚣山迎請池府三王，並至廈門鈴仔堡二王爺街隨行，順利登岸後，於塗葛窟牛埔仔庄定居，並至南鯤鯓代天府迎請朱府王爺為大王，合稱「牛埔三府王爺」。
而永順宮薛四王及吳五王，又有另一典故，地方相傳薛府千歲原供奉於臺中東勢，後因溪水高漲，廟宇流失，因而寄放於巧聖先師廟，吳府千歲則為清水高美文興宮所供奉之王爺；某日，一位信徒至東勢請走薛府千歲後，又至清水請走吳府千歲，但到牛埔仔要偷請池府千歲時，被路過民眾發現，倉皇逃跑，得手之神像也未能帶離，當地居民認為這是薛、吳兩位王爺同受玉旨到牛埔庄坐鎮，輔佐三府王爺代天巡狩，遂合稱為「牛埔五府千歲」。
光緒11年（1885），王爺降乩指示牛埔仔庄將會流失，乃遷徙至崁仔頂，並由龍井南寮信徒提供茅草，於永順宮現址重建廟宇，才得以避開明治44年（1911）塗葛窟流庄的命運。
明治29年（1896）奉旨代天巡狩四個月，巡狩虎尾溪以北、大甲溪以南、東至中央山脈、西至海岸的彰化縣轄境，巡狩完畢後，迫於時局未能舉行送王儀式，該批巡狩王爺神像、文武主帥、3對劍童印童，以及36尊兵將乃於該宮供奉迄今。
昭和5年（1930）翻修屋頂及建設左右廂室，現廟於民國63年（1974）重建，民國68年（1979）落成，民國71年（1982）購廟前500坪土地建活動中心及村民集會所，民國86年（1997）再購廟埕左側400餘坪土地，民國93年（2004）興建辦公大樓，始具今貌。
1、曾經有一進香團至水裡港福順宮進香，途經永順宮時並未放鞭炮行轎致意，結果回鑾進廟前，乩童起乩指示兵馬被永順宮張二王子扣押，需趕至永順宮談判，眾人遂又到永順宮，此時永順宮老三王降駕叱責該宮未行禮一事，並指示張二王子只是囝仔，何須勞師動眾，此時，張府二王又降乩緩頰指示可歸還兵將，此事才落幕。
2、民國88年（1999）以前，薛府千歲至東勢巧聖仙師廟參香時，因該廟並非薛府千歲原廟，故其神尊都不進廟，民國88年（1999）九二一大地震發生後，永順宮辦理乩事時，薛府千歲近兩年沒有降駕，信徒們認為這是因為薛府千歲神駕回到故里賑災，爾後，若到東勢參香時，薛府千歲便會進到巧聖仙師廟駐駕。
3、永順宮五府千歲信仰分工如下所述：由朱府千歲掌管安太歲，每年安太歲後，永順宮會將信徒安太歲疏文綑成束放置朱府千歲鎮殿神尊神衣下，待謝平安時才取出焚化；張府千歲在天庭尚有官職，為二部天官，並擅長觀地理，故信徒新婚或建屋時，皆會迎請張府千歲；池府千歲擅長治療陰病與遊地府，較難處理的事伔亦多由池府開辦；薛府千歲與吳府千歲為協助三府王爺救世濟民，故平日信徒生活中所遇疑難雜症，多由薛府與吳府降駕處理。
4、1990年付，有一位村民即將臨盆，但胎位不正，焚香向二夫人媽祝禱後，生產時胎為轉正，母子均安。
祭祀活動:
大肚下保20庄迎媽祖
每年農曆4月初10迎請彰化天后宮內媽祖、彰化南瑤宮南門媽、大肚萬興宮頂街媽、大肚永和宮下街媽至境內賜福。
進香
王爺有指示才會辦理進香，一旦辦理進香，便連續進香三年，進香地點視王爺而定，朱府千歲若有指示要進香，便至南鯤鯓代天府進香；薛府千歲有要指示要進香，至東勢巧聖先師廟；吳府千歲有指示要進香，則會至高美文興宮進香。進香人數約1500至2000人。
許平安
農曆正月初4至15日之間擇日辦理，儀式進行時會敕布符供信眾求取。
普度
農曆7月15日辦理。
謝平安
農曆10月16日辦理，與朱府千歲聖誕合辦。