教會在1994年開始，啟動了建堂的事工，先在當年二月成立擴堂研究小組，專責研究擴堂或改建之可行方案，並於同年6月發信給地政署，申請撥地興建新堂，並聘請呂元祥建築師為本會擴建顧問，經與政府初步的商議，教會於95年3月向地政署申請品蘭街的地段，作為換地重建的選址，並開始提供有關新堂的建議，由於當時教會仍未就品蘭街的地段作出共識及決議，故將此方案擱置。


至1998年，舊啟德機場遷出，而教會得一機會於當年七月在舊機場原址舉行祈禱會，有8000多人出席，成為當時盛事。另外因本會已啟動了換地重建之申請，城市規劃委員會於當年九月將本會原有之地段，重新規劃為住宅（乙類）用途，換句話說，教會若完成重建遷出原址，原地址便可以興建住宅樓宇。教會立即積極探討在東南九龍物色新址之可能性，並於同年10月向政府申請東南九龍之地段，作為建堂的新址，並向政府提供新一輪的申請建議書。但由於各種的因素，東南九龍的規劃及發展遭到擱置及延誤，教會在該地段之申請新堂址的進展，至2002年停頓下來。


2002年，教會重新委任一顧問公司，代為物色其他可供申請的地方，並提供了另外三處的地段，包括東利道之選址，其中之一為延文禮士道之地址，但後來遭教育統籌局反對，因該地已訂為一新校之發展，直至2005年4月，教會在房屋規劃地政局的官員安排下，與該局及規劃署、地政署之官員開會，可讓教會考慮申請東利道之地段，並提供有關之資料，教會便再邀請另一顧問公司，進行教會原地重建、品蘭街及東利道之地址作初步的環境的評估，經年多的討論，教會就過去各項的可能性作出檢討及比較，並未來東南九龍的發展，東利道的地段是適合本會的建堂需要，故在向會眾推介及諮詢後，正式提交月會通過。