新山广肇会馆成立於1878年，由已故新山开埠先贤黄亚福先生发起，联同广肇两属热心人士所创办，藉贯连络桑梓之感情及维护同乡之福利，至今已有百多年之历史。
新山广肇会馆初期设於明里南街与兆镇街交界处之板屋，做远路乡亲居停之所，斯时交通工具俱用牛车，而居於丰盛港、任罗宏、德兴港等地之我二属商界及劳工，因有会馆之设，咸称方便焉。
当时之总理为已故黄亚福，以馆址之後座为乡人养病及丧事停柩之所，并授谭富主理其事，继之为黄恩及秦根南。
迨至1906年，黄亚福慨然赠送兆楠街二店铺及一地段，作为我馆之新址，随即公选黄广林、黄莆田（亚福）、黄燊南、陈礼亭、陆成铎、张椿广、朱香渠、骆雨生、冼志棠、陆秋杰、黄義初、伍诏南为倡建大总理，庆云居、义利店、同济堂、广南利、祥元号、南利栈、冠珍居、广福田、广益隆、广祥号、郑廷禧、黄光荣、陈玉衡、黄权标、林八为倡建大协理，於是发动募捐，在各同乡同心协力之下，筹得钜款，款既备，即鸠工兴建， 1907年落成，遂乃迁入。
今日我馆之堂皇，盖得力於黄亚福与诸总理及协理，尚有捐款诸君子，其功不可抹也。
1907年，本会先贤黄羲初，骆雨生以其远大之目光，洞悉时弊，盖当时当地竟无华校之设立，以致富家之子弟，遣送回国求学，贫穷之家者，其子弟则游荡以度日，竟无学校可资收留，如此社会，岂不悲哉？乃鼓吹兴办学堂，鼓励同乡创办育才学堂，以资培植同乡子弟，兼收外籍学子，四出奔走，礼聘黄伯长先生为校长，用本会会所为教室，授课四年有期。
本会兴办育才之初，曾引起同侨之注意，而黄羲初亦向同侨鼓吹兴学之宏旨，咸认善莫大焉，於是本会为促成华侨大团结以兴学，起带头作用，乃发起创办公立宽柔学校，大收将伯之效，时为1912年（民国元年壬子）。
公立宽柔学校成立，既达成功，本会之创办人黄亚福，荣膺该校首任总理。骆雨生、黄羲初也分任要职。时为1913年（民国二年癸丑）2月1日，开学上课，同年5月18日举行幵幕典礼，於是饬令育才学生全体进入宽柔学校就读，由本会负责保送，而本会创办之育才学堂，亦於是年宣告结束，由此既可想见我会对同侨教育之贡献。
1939年，当黄羲初担任本会总理时，发起扩建会所，以适应实际之需求，乃由黄羲初总理领衔，向政府申请与本会后座毗邻之一段地皮675尺(深15尺，阔45尺）赠予本会，并会同元老陈玉衡，同往星洲，晋谒本会名誉总理拿督黄兆珪（柔佛州参政议员)道明来意，请其协助进行，既荷允许，不数月即获得政府之批准，将该地皮慨然赠予，本会遂将原有地契呀兰交由政府重新更正，以便管理，事既成功，同仁莫不欢欣，并加建围墙以护之，先贤苦心争取，维护本会之基业，其功绩是不可磨灭者也。
1945年8月15日，日本接受波茨坦宣言，作无条件投降，第二次世界大战告终，本会在全体同乡大力支持下，迅速筹备复办，以新山华人注册社团而论，本会乃最先复兴者，当年会长为苏炳衡，总务赵孟华，财政高汉光，并进行募捐以修茸会所及购置家具，内外粉饰，使之焕然一新，备受各社团之注意，当年本埠各社团筹备复兴会议，多有假借本会举行，咸称方便焉。
1955年，本会成立国术醒狮团，其目的乃引起青年们之兴趣，发起人为苏炳衡、高汉光、伍庭想、李权、郑照、吴锦华、朱寿华等，乃於当年礼聘国术名宿吕荣添为教练，除广肇籍外，兼收外籍青年，参与锻炼，多年以来为社会福利，慈善，教育服务，皆具成绩，贏得公众人士好评。
1955年，当值会长高汉光，副潘霖端，以我馆之章程，已属陈旧，多有未适合时代者，如每年仅向会员徵收年捐以维持会馆之经常费用，特别捐则例外，於是召开同人大会研讨之，经指出此乃过时之章程，实有修改之必要。
在全体会员赞成通过之下并修改之为每一会员须每月缴交月捐一元，特别捐则例外，此後会务蒸蒸日上，朝气蓬勃，组织粤剧部及兵乓球队等之设，皆为号召青年之康乐活动， 1945年以来，会长为苏炳衡，潘霖端，高汉光，陈宣，正副更替。
1965年，本会发动筹建广肇会馆大厦，公推拿督黄树芬为扩建委员会主席，惟因图测未获当局批准，直到2000年，本会在理事会员们众志成城的力量下。终于在百万镇购置了一间三层楼的新会所（No。7， Jalan Permas Jaya 9 / 1，Bandar Baru Permas Jaya， 81750 JohorBahru )，以供各小组作为专属活动中心。
自本会成立後，由黄亚福担任总理，他蝉联总理一职多年， 1939年，由黄羲初接任总理，1942年至1945年日治期间，会务被逼停顿，直至1948年才开始复办，复兴後，首届会长为苏炳衡，其後继任会长有高汉光，潘霖端，关福南，均各蝉联会长职务多届， 1980年起，改由曾振强博士接任会长一职。
本会於1978年庆祝成立100周年会庆，当年也出版《新山广肇会馆一百周年纪念特刊》，於2001年庆祝123周年会庆，再出版《新山广肇会馆123周年纪念特刊》， 2008年，本会再出版《新山广肇会馆一百卅周年纪念特刊》，以欢庆创馆130周年纪念，这三本特刊各载有本会史略及各项会务活动报告。 为了跟进云端电脑化时代的发展步伐，本会在主席伍天就及理事会仝人的齐心协助下，与时并进，设立本身的官方网页，并于2015年12月1日(星期二)假新山新湖滨豪华宴会厅举行的创馆137周年千人晚宴上，举行云端网页推介礼，为本会迈入电脑化时代作业奠下历史的根基。
随着官网的设立，本会未来所有历史跟进及最新活动资讯，将陆续上载网页云端，让分散全球各地的会员，随时随地都能了解会馆动态，减免与会馆脱节的问题发生。随着电脑化计划的落实，也意味着本会开始迈向另一个时代的旅程碑，更开拓了本会逐步系统化及年轻化的发展理念目标，期望这个计划能为本会注入另番新气息，迎向时代的最前端。
