主後1978年元月1日，赤峰街教會為紀念設教廿週年，於石牌與北投之間的新社區中，租下尊賢街249巷23號1樓，開設「吉利佈道所」。草創初期，王再興牧師與王謀祥長老卯足全力，耕耘澆灌，終能奠下堅固根基。

　　初期的聖工均由母會之長執輪流負責，同年3月聘請蔡維禮牧師兼任開拓事工，開始時的聚會人數只有10人左右，經過蔡牧師伉儷之努力，教勢日盛，特別是主日學學生曾高達五十人，半年後，由於附近也有一所道生長老會吉利教會，為避免混淆，乃更名為「尊賢教會」，並於次年5月遷至尊賢街251巷12號1樓。同年8月蔡牧師離職，教會事工轉由神學生楊耀弘負責。至次年7月底，楊先生受派至他教會牧會而離開。

　　1980年７月母會有意籌募本會建堂基金，以便購買聖堂，經王謀祥長老多方尋找，乃以總會新台幣265萬元購買現址（建坪約40坪，空地20坪）作為聖殿。同年10月，由台北中會傳道部調派陳宇光教師前來牧會。母會鑑於本會之人力、財力均足以自立自足，乃於1981年6月7日舉行首次會員大會，選出第一任長執，並於8月30日升格為堂會。次年2月21日，選聘陳牧師為本會首任牧師，並於4月11日舉行獻堂暨封牧就任典禮。

　　本會一向注重社區傳福音之工作，自陳牧師接任本會牧養工作後，即不遺餘力展開一系列的暑假活動，學期中也舉辦國中生課業輔導，藉以鼓勵學生參加聚會，成效非凡。本會遂於陳牧師以十年心血苦心經營，並得到歷任長執同心協力，而有今日建樹。1990年8月底，陳牧師應雙園教會之聘而離任，隨即由穆信智牧師接棒，再謀教會之進展，同年10月22日，為使原禮拜堂容納更多人聚會，並更新裝備，「建堂修建委員會」動工整修禮拜堂，二個月後竣工，在外觀上，尊賢教會遂擁有一座精巧雅緻之聚會場所，同時，在內涵上也同心力求求質量之增長。