简史
一、前史
1815年来自德国、瑞士、法国、奥地利等国热心的信徒及牧师，为了实践主耶稣基督所托付之大使命，即传福音到世界各地。在瑞士的巴色城成立了一个以宣扬福音为目标的差传机构，定名为“巴色传道会”（Basel Mission）或译为“巴色差会”。
巴色差会在开始时先派宣教士到东欧及非洲宣教，1833年则差派宣教士到印度宣扬福音，建立教会。到了1846年，巴色差会回应中国客家人“马其顿呼声”而差派瑞典籍韩山明牧师（Rev. Theodore Hamberg）和德国籍黎立基牧师（Rev. Rudolph Lechler）前来中国，向广东省及香港的客家人广传福音。经过一段年日，突破了诸多困难，终于在广东各县及香港建立了174间教会，100多间学校（包括小学、中学、盲人院），和一间神学院，两间医院，会友达数万人。
广东巴色会于1924年改名为“中华基督教崇真会”，香港之巴色会于1928年更名为“中华基督教崇真会香港区会”(取其“崇拜真神，崇尚真道”之意义)。再后于1952年定名为“基督教香港崇真会”。
二、立会
1882年，北婆罗洲渣打公司为了开发北婆罗洲（即今日的沙巴），特派专员到香港和中国巴色会当局洽商，招募客家人来此开垦。当时回应此召募者，有十余家庭。这第一批移民多在古达老山芭垦植，平日从事耕作，到了主日则停工休息，并在其中一个家庭聚会崇拜。直到1886年，在上帝的带领下，于罗泰丰山芭建亚答礼拜堂一座，成为北婆罗洲本会第一间礼拜堂——老山堂。1886年，有数百信徒由李祥光和黄旭明两位弟兄的带领下抵达古达。
1902年，巴色差会才派遣牧师前来主理会务、施行圣礼。巴色差会差派的牧师，尤其是在1915年之前，都很积极在帮助教会向政府申请地段作建堂、建校之用，也在经济上大力支持。巴色差会没有停歇在德国、瑞士、中国、香港召募、派遣教牧人员，以及教员前来北婆罗洲。因此，教会茁壮成长，迅速在各地植堂。单在13年间，共建立了7间堂会，13间学校。
巴色会最初期的20年，即是1882年至1902年前来北婆罗洲开垦种植的信徒，多为赤手空拳的贫苦信徒，建立家园外还要负起建立教会、维持教会，又要办理学校等责任，彼等均为主付出相当的力量。
三、自立
巴色差会代表施灵光牧师（Rev. Schule）于1924年从欧洲回来重理会务。1925年，适逢古达埠堂立会25周年感恩纪念盛典，本会东西海岸各区九个支堂均有代表出席。施牧师乘此机会于半路坳牧师楼召开第一次联合会议，即是后来称为“第一届般鸟巴色会总议会”，会中施牧师建议，本会应实行自立，成为自立会，以便善用教会各方面之恩赐，维持及发展教会。当时本会先贤领袖们虽认为自立的时机尚未太成熟，毅然通过接受施牧师的好意，遂决定成为自立、自养、自传的教会。
本会在实施自立后的首任会长为黄天玉牧师，当时教会全体依靠上帝的大能，并在前贤的领导以及全体信徒群策群力之下，教会继续稳健发展、向前迈进。
四、创伤与重建
日本军国主义者于1941年进军侵犯东南亚各个国家。从1941年至1945年之间，本州人民惨受日军之蹂躏，当时本会信徒直接惨死于日军手下者约有80名，间接而死者达数百人；另外教堂被焚，校舍被炸，住宅被毁者甚多，信徒四散，教学停顿，生活痛苦至极。
1945年日皇无条件投降后，本州在日军浩劫之余，满目疮痍，触景伤心之下，信徒们重整家园已感吃力，而对教会、学校之重建工作，乃心有余而力不足；其时幸得巴色差会，AUGUSTANA LUTHERAN CHURCH及信义会（LCA）伸出援助之手，慨然以金钱及人力（指教牧、校长及老师）协助本会，而使本会不仅迅速恢复旧观，甚而更具规模及活力，这种肢体相顾，雪中送炭的情谊，深深表现主里的爱心，这也成为本会日后加入世界信义宗联会（Lutheran World Federation）主要因素之一。
五、教会结盟
本会基于体现合一的见证，在1973年与沙巴复原教会 (Protestant Church In Sabah或简称PCS)成立了华土联合委员会；稍后又与马新信义会（LCMS）、福音信义会（ELCM）及沙巴复原教会成立“马新信义宗联会”(The Federation of Evangelical Lutheran Churches of Malaysia & Singapore)。
1979年，本会成为世界信义宗联会（LWF）的成员。在这过程中，本会与巴色差会（现称为使命 21【Mission21】）之间的关系从未改变。教会与崇真会（前身为香港巴色会）保持着联系。本会也是马来西亚基督教联合会（Christian Federation of Malaysia）、马来西亚基督教协进会（Council of Churches of Malaysia）和沙巴基督教协进会（Sabah Council of Churches）的成员。
六、差传
在本会所推动的差传事工方面，虽在过去曾协助“沙巴复原教会”的成立，但因能力有限，所作委实不多；1967总会与山打根堂合作接办由一位加拿大医生宣教士Dr. G. Christopher Willis 于东海岸拉卜河流域模乐乡村设立友族宣教中心及医务所后，本会在本地跨文化差传事工上有了一个新的里程碑。惟本会自动自发积极向友族展开传福音的工作，乃始自1974年由夏南南堂会之张永良、钟惠忠等弟兄所发起向友族传福音的运动。由于此圣工发展快速，信主人数激增，稍后便交由亚庇区会与总会全面负责。
本会国文部事工逐步稳健发展，堂会及会友人数亦日益增加，教牧人员的需求量相应的提高，教会遂于1980年在亚庇升旗山亚庇堂旧址设立“圣经训练中心”，借以培训国文堂会教牧以及领袖人才。由于顺应时代的需要，此圣经训练中心于1988年被升格为“沙巴神学院”。
为使本会各语文堂会能更有效地拓展圣工，并稳健发展，而制订新的组织架构。2003年第31届总议会时正式通过新的组织架构，成立了中文大会以及国文大会，2009年第34届总议会正式通过成立英文大会。
乘21新世纪的到来，本会举办2000福音大会，教会领袖聚首商讨制定未来福音策略，其中积极回应普世宣教的需要，毅然定下“立足沙巴，走向世界”的福音策略，决心落实酝酿已久的海外宣教目标。除了推动短宣与植堂事工外，并定中国客家地区以及马达加斯加为本会海外宣教焦点区，同时支援宣教士在中国、澳洲柏斯、吉尔吉斯等地宣教。