話說明朝末年的一個晚上，數十名漁民正在南鯤鯓沙汕上捕魚，忽然從海上飄來一陣鐘鼓管弦的樂聲，並且出現一艘三檣的大帆船，緩緩駛進南鯤鯓灣。隔天，這些漁民一齊到港口看個究竟，結果只看到一艘破舊的小船停在岸邊，裡面載著六尊神像，分別寫著：「 大王李府千歲、二王池府千歲、三王吳府千歲、四王朱府千歲、五王范府千歲、中軍府」，以及一支神木和「代天巡狩」的旌旗。
漁民於是將這些神像供奉在草寮內，早晚焚香膜拜，結果從那天起，漁民只要出海捕魚，一定滿載而歸。從此神威廣播，信徒也越來越多。後來有人提議建廟來供奉神明，但是因為財力不夠，只好祈求五王另外找尋吉地。在隆重祭祀之後，漁民們恭送王船出港。想不到出港不到一佪時辰，王船竟然又逆流返航，而且停靠在原來的地方。漁民驚訝不已，並認為五王打算長駐在這裡，所以再次恭迎上岸，安奉在草廟中祭拜。王船逆流返航的神蹟遠近轟動，朝聖謁拜的人絡繹不絕，居民的生活也因為漁獲豐富，而日漸改善。
後來沿海居民感受到神恩浩蕩，再度提議為五王建廟，於是有錢出錢，有力出力，建廟工程正式展開。這時三王吳府千歲親自起駕，選定吉地在南鯤鯓的南邊，大王李府千歲也大顯神通，將金紙變成白銀，並且化成漁民遠渡福州買杉、泉州購石、漳州沽磚瓦，又租船將這些建材運回南鯤鯓，隨後展開建廟工程。神廟建築期間，泉州名雕刻師「媽福師」受五王託夢，隻身來台雕刻神像，原王船內的神木劃有六段，媽福師依指示取前五段雕刻成五王金身，第六段雕刻成中軍府，也就是現在所說的「開基正身」神像神像完成後，五王選擇吉時於四月二十六日午時開光點眼，由高功法師主持，點睛後神像鏗然有聲，振動不已，其中三王振動最為激烈，足足有半個時辰之久。在大家的通力合作之下，終於在康熙元年（西元1662年）完工，稱為「南鯤鯓廟」
因為是開台首廟，所以也叫做「開山廟」，而五府千歲也因此被尊為「南鯤鯓王」。五王建廟所在的南鯤鯓沙汕，在地理風水上屬於「浮水金獅活穴」。這裡有三件寶物：一、白 榔樹：相傳急水溪是一條盲龍，無法自行向流。而白糠榔樹生於廟後，是浮水金獅的尾巴，急水溪就是靠獅尾的招示，左沖右轉，九九八十一轉後才能到達海面，也因此鯤鯓山才能免除山洪的侵襲。二、白馬鞍藤頭：這件寶物生在海底，根藤密佈纏繞，具有保持水土和轉海水為淡水的功用。三、烏金石：位於「石井崙」的井邊，是漁民汲水時的踏板，相傳可以避水氣，更可以防止海水倒灌。鯤鯓三寶的地靈顯赫，使得「鯤鯓王爺」的神威更加遠播。
不料，有一天來了一個和尚，這個和尚曾因破戒，遭受過五王的譴責，因而懷恨在心，知道五王在這裡建廟，特地前來報復。他利用夜深人靜的時候，砍倒白康榔樹，並挖出樹心而去。後來，荷蘭人（昔稱紅毛番）又盜走烏金石，並且掘取白馬鞍藤頭，於是南鯤鯓的地理風水盡遭破壞，不久，山崩海嘯、山洪暴發，南鯤鯓海汕就這樣慢慢被海水吞沒了。自從南鯤鯓海汕被破壞沈埋後，五王就開始重新尋找吉地，準備遷建，以便執行「代天巡狩」的職責。有一天，三王吳府千歲親自起駕，直奔 榔山，並卜得「虎穴」吉地，打算當作第二次建廟的地點。康榔山的地權原本是屬於鹽水港茄苳腳吳公烈先生所有，山中有一塊直徑二尺的圓形地，四季不沾露水，大雨不濕其地，就是「虎穴 」。吳公烈多次請地理師尋找，但都沒有成功，後來得知三王爺起駕勘得「虎穴」，驚嘆之餘，便將該地恭獻出來做為建廟的用地。康榔山向來為「囝仔公」所佔領，囝仔公生前是一個牧童，死後葬在這裡，因得到靈氣而成神。
囝仔公知道五王要在這裡建廟，馬上提出抗議，說：「這塊地是我生前所有，埋有銅針為證」。五王反駁說：「我們早在渡海來台時，就已經看中此地，並埋有銅錢為記 」。雙方會同土地公相驗，結果：「銅針」插在「錢」孔之中，無法公斷。雙方由爭吵轉為武鬥，囝仔公召集陰兵陰將和五王展開一場「神鬼大戰」。後來，赤山嚴佛祖知道這件事，就請天上聖母和保生大帝出面協調，雙方訂下契約：一、五王代囝仔公建小廟。二、大廟來進香，小廟必有敬。三、有福同享，光大南鯤鯓香火。現在三王吳府千歲的神像額頭有一道傷痕，就是當年那場大戰所留下來的英勇標幟，廟方曾經多次請工匠來修補，都無法成功。戰火停息，建廟工程於嘉慶二十二（西元1817年）丁丑二月晦日正式動工。但是工程浩大，建材物資相當缺乏，幸好有麻豆民婦郭鳳，受五王托夢，乘坐烏轎前來，捐獻白銀一千兩，使得工程能夠順利進行。
道光二（1822）年六月六日完工，取名為「南鯤鯓代天府」，整個建廟工程先後歷時五年又四個多月。後來又在同治十一年（西元1872年），增建後殿「青山寺」，崇祀觀音佛祖，以紀念當年調停的功勞。日據時期，廟後的急水溪常常氾濫成災，嚴重影響到廟地的安危，並使得廟和北 榔山幾乎隔離斷絕，往來只能依靠排筏。沒多久 ，「囝仔公」首當其衝被洪水沖垮，後來只好遷徙到代天府東北處暫住。民國六年，廟宇距離支流僅十來步，南鯤鯓廟岌岌可危。這時，五王起駕，畫了七張「犁頭符」，然後命人購買犁頭七個、大鑼二面，前往祭溪。作法完後，廟南尖地逐漸浮復。隔年，廟方奉五王指示，發動善信二萬餘人築堤護廟，不出數月，堤防築成，稱之為「五王堤」。五王堤完成後，南鯤鯓已沒有後顧之憂，「囝仔公」於是遷回原地重建小廟，廟稱「萬善堂」，神稱「萬善爺」，並雕造金身和鎮殿金身各一尊。
民國九年（西元1920年），北門庄王謀等人，看見廟宇年久失修，於是提議擴建，經過三年的募款，一共募得三十萬元的經費，於民國十二年（西元1923年）二月一日興工，並遵照神明的指示：不動爐位，增高增寬。民國十七年（西元1928年）四月二十六日舉行入廟大典，但是整體擴建的工程一直到民國二十六年（西元1937年）二月才全部完工，前後一共十五年。除了正殿的修繕之外，還增建了中軍府、城隍衙、青山寺、天公壇、娘媽殿等，也就是今天所看到的廟貌。(資料來源：南鯤鯓代天府全球資訊網)
