兩百多年前，中國連續遭逢水災與旱災及盜匪禍害；延續廣東省各縣的鄉鎮，使赤貧者無立足之處，富裕者無法安居樂業，生活提心吊膽艱苦，先輩們為了尋求穩定的生活，接濟家鄉的親人，遂促使廣東三府同鄉結伴出洋，跋山涉水，飄洋過海，其中少數來到了納閩島。偉大的先輩懷著美好的憧憬，開始了艱辛的拓荒歲月，靠著雙手合無比的毅力，改善自己的命運，同時也造就了納閩島成為一片繁榮的新天地。
汶萊蘇丹於公元 1846年12月18日，在英國的要求，被迫簽訂一項契約，把汶萊的納閩島，割讓給英國。 1847年，英國殖民地政府展開策劃開發已改名為維多利亞的納閩島，並從香港物色土木技術人才，到來興建政府行政辦公樓，也為英國官員興建官邸，同屬英國殖民地的香港，多為廣東省人氏，所以英政府招募技術人才，大部分歸於三府同鄉，這是第一次三府同鄉大量到達維多利亞島工作。
公元1849年，英國東方群島公司，開始在蘊藏著豐富的煤礦納閩島北端開採，直到公元1852年，開採規模擴大，島上同時鋪設一段煤炭運輸鐵路線，便需更多勞工，公司再次從香港引進大量勞工，這是中國人第二次大規模南來納閩島。
由於當時到煤礦山工作的人數眾多，為了團結三府人士，為同鄉謀求福利，有必要組織起來，在一班先賢策劃發動下，成立了廣惠肇會館。
廣惠肇會館和廣福宮原是同體。會館和廣福宮的啟發人是相同的，目前所能見到最早有關五位先賢的名字，翁觀聰、梅彬遠、李玉昆、黃長才及黃二妹的碑文紀錄，是在廣福宮匾牌上記載了時為咸豐二年（即公元1852）及木雕對聯，刻著“廣惠肇眾弟子叩謝”，印證廣惠肇之存在。
先賢對三府同鄉在社會作出過重要貢獻，無論是對於當地的建設、同鄉的信仰活動、教育事業、以及養生送死的慈善事業，他們都帶頭出錢出力，先後置業創設會所。早期先賢遠渡南洋，預知返鄉遙遙無期，落地生根之餘，遂發起設立百年歸老的安身之地義山，並著手購買或募捐葬地。
以當時會員之間時常發生口角及毆打事件，英政府見此情形，故有不可收拾之慮，集勒令封閉會館組織。這也促成會館進入第二階段的歷史，把會館組織改為英國政府允許的神廟組織，即成立協天宮。除了供奉關聖帝君、玄天上帝及華佗神醫，當時還有供奉華光大帝，於粵劇戲班演出開鑼前必祭拜。神廟內也設立恭敬堂，安置過世同鄉之神主牌，尤其是那些沒有子祠的先賢，交託會館代為祭祀先人。
1942年，日本南侵，維多利亞島淪陷，改名為前田島，導致會務停頓，時至聯軍空軍轟炸，島面經過炮火洗禮化為平地，會館一切均毀於戰禍，蕩然無存。
1945年聯軍登陸，日軍投降，本島光復，會館重新操作，協天宮嚴重損壞，炸毀後再修葺，安置神位供會員膜拜，會館樓上租於業餘俱樂部會所，會務逐漸恢復正常，會員也重新活躍參與會館活動。
1947年，會館理事會重新組織起來。一位任職夏利臣洋行買辦的鄉賢譚蔚文，在會所開辦私校，供書教學，教育同鄉子弟，備受同鄉讚賞。這時會館再度正名為廣惠肇會館，也即是第三階段。
1946至1955年，英國殖民地政府推動“戰損賠償”及“市區重建”計劃，會館成立一個以江添盛會長為首，成員包括胡天祿、楊錦泉的委員會負責，時任市議員的江添盛也被政府委派到亞庇考察，了解有關亞庇市區重建計劃，協助市政局規劃重建。
1953年第3屆理事會一代時，會館在市區唯一的產業乃協天宮，位於現址大眾銀行對面位置；市政局重新分畫土地，根據原有建築物面積，因此會館獲得一間半店位，又經抽籤分配獲得Liberty街72號一間店位，以及半間位於Mundy 街86號、另一半為益源寶號擁有。會館也因為戰損索償手續因素，於1955年12月9日又從會館組織改為神廟組織。
1955年第5屆理事會，在銀行貸款下以RM42, 000.00及RM18, 000.00購買以上的一間半店屋，會館也委託江添盛會長全權處理，一人簽署所有文件，每月償還銀行貸款，會館財務非常吃緊，當時財政陳之驥撙節支出下，會館租出店屋，只使用會館擁有半間店面的樓上為會所，除了會議廳，還供奉神明及先賢的神主牌。
1961年本會會長李宗顯聯同潮州瓊州會館，託林殿記安排居汶萊黃新安共同洽商，恢復廣東義山14英畝地契的擁有權，1967年政府開闢Jalan Rancha-Rancha，墳墓影響了築路工程，需要搬遷讓路。三會館始成立“廣東義山委員會”處理之，至1973年共搬遷完畢受影響墳墓計有二十三穴。
1968陳道宏擔任會長，立即處理社團註冊問題，從神廟組織改回會館組織，到亞庇廣肇會館及客屬公會考察，聘請律師修改章程，增加產業信託人至三位，同時也把每屆任期改為兩年。
1970年第20屆理事會啟用新章程，當中有連任七屆副主席的劉貴出任秘書長，連任三屆幹事的桂銘生出任總務，理事會正式設立婦女組，第一任主任為陳明順，直到1974年由會館第一位女性理事尤金蓮擔任。會所同年七月搬遷至海旁街 63號，尤合全為主任的康樂組也同年為會員設麻雀娛樂。
1972黃植濂會長積極推行會員子弟獎勵金及獎學金，並以次年四月首次頒發獎勵金。 1972年政府批准三間會館購買毗鄰十二英畝原屬江夏堂墓地，會館各出資二千元，有關地契與1980年獲得，使廣東義山擁有二十六英畝墓地。
1974年會員大會通過授權理事會購置三層店鋪。 1975年修改章程唯會長任期為五屆。 1976年沙巴州政治趨勢演變，華人傳統新春舞獅禁令解除，會館總務桂銘生和陳仕業組織醒獅團，由陳明順指導下，發揚傳統舞獅文化。黃植濂會長及理事陳榮忠醫生受委本坡市議員，會館申請成為沙巴崇正獨立中學團體贊助人，並捐獻RM1,000.00為建築基金。
1977年新春組織麒麟團賀歲，是時為唯一會館同時擁有醒獅團及麒麟團，會館在福利組伍伯恩籌備下，首次在海景餐廳舉辦敬老會，此項活動為三年一度一直延續至今。
1978年宣示支持華教，會館醒獅團為獨中基金新春募款，成功籌獲RM5, 877.50，會館也另外捐獻 RM12, 000於獨中基金。納閩廣福宮開幕典禮，會館派出醒獅團，高蹺隊及花車參與其盛。
1979年第 25屆會館理事會終於落實購置四層角落間店鋪，同時決定出售本會半間店鋪。再次捐獻五千元於獨中基金。 1980年會館醒獅團為啟華幼稚園籌獲 RM7, 239.62款項，1982年新春再為啟文學校籌獲 RM20, 837.93建校基金。
1987年曾耀宗由拿督黃植濂手中接過棒子，陳榮忠醫生任副會長，曾耀宗會長吸納更多年輕人，新人王國富任秘書長，協助會長擴大會館組織，會館也搬入四層店鋪四樓。
1989年伍伯安接任副會長，成立一個張鳳蓮為首，鄔玉英、何麗紅在尤金蓮元老輔助下婦女組團隊，周金賢團長、廖光海、陳慶麟及劉錦華等組織青年團，同時青年團武術組陳匡維及李君忠等負責醒獅團。
1990年陳觀帶、馮德成、孫瑛等，基於會館所有神明及先賢神主位,安放於會館五樓天台一房間神龕內，沒有恭敬妥善處理，認為對神明及先賢為之不敬，帶領的協天宮重建委員會，負責重建協天宮，以紀念先賢成立協天宮的精神，重新設立恭敬堂供奉先賢神主位。
1993年張鳳蓮、何麗紅分別成為會館第一位女性秘書長及副秘書長。
1995年會館主要職位之一，秘書長再次由女性鄔玉英擔任。
1995年曾耀宗會長及歐保振交棒陳智琦、陳慶麟為正副會長，由於會員人數增加，需要更大空間舉辦活動，理事會決議購買新會所。
1996年再度修改章程，理事會增添署理會長一職，由陳慶麟出任。 1997年 9月成功舉辦 “146週年五大慶典”，恭請丹斯里黃植濂為主理嘉賓為四層樓會所主持開幕。大會通過捐助 RM30,000.00於納閩啟文學校一間以會館名譽命名的課室，也贈送一台二手油印機於中華學校，為迎合科技時代會館購買電腦及復印機。
1999年策劃購置貨倉，獲得會員大會通過，會長陳智琦局紳成功為會館購買目前會所，2000年為青年團，婦女組草擬簡章，起草廣東義山細則，會館章程修改及翻譯，2001年搬進目前貨倉樓上為會所。 2002年成功舉辦150週年會慶，
2003胡鎮源會長連同海南及潮州公會，積極進行義山大型美化工作，今天義山的成績是三族工會一同努力下的成果。 2010年大會決定籌辦“成立160週年慶典”。
2011年專業人士的新人黃慧彬加入會館任署理，陳匡維重返理事會出任秘書長，胡鎮源及黃慧彬，財政何少強及理事羅正興領導的團隊立即對會務進行革新，會員資料更新及數碼化，電腦配備、帳目管理系統軟件更新，成立以尤健盛為首的160週年慶典工委會，在理事會、青年團及陳永結團長、婦女組及劉道箐主任及協天宮小組配合下，積極進行慶典籌備工作。
2012年初秘書長陳匡維獲得聯邦政府委任，出任納閩機構諮詢委員，本會名譽會長拿督陳智琦太平局紳也曾經出任納閩機構諮詢委員，會長胡鎮源、署理黃慧彬及總務廖光海共同負責成立小組，為會館添置傢具，增置Wifi供會員上網，掃描歷史相片存檔，收集資料，配合科技時代署理黃慧彬負責設立會館網頁，秘書長陳匡維負責草擬撰寫會館簡史，配合160週年出版紀念特刊。
協天宮於關帝誕當日重組醒獅團，在會長胡鎮源、署理黃慧彬捐贈兩隻獅頭，隨後協天宮主任陳泰安及醒獅團團長陳錦坤為醒獅團團員展開積極訓練活動。
今年是納閩廣惠肇會館 160週年。這一年是會史上具有里程碑意義的一年，它開啟了我們會館生生不息，蒸蒸日上，永創輝煌的新篇章。會館的精神將會通過我們一年又一年的努力，一代又一代的傳承而發揚光大。這將會在會館的歷史上寫下絢麗的一筆，經過的時間的檢驗，他宣示了一個新時代的到來！