다락골에서 점차 생활이 넉넉해지고 또 외교인 친척들과의 접촉으로 인해 신앙생활이 해이해지자 최경환은 보다 자유로운 신앙생활을 영위하고자 형제들을 설득하고 그들과 같이 서울로 이주하였다. 그러나 3년 만에 천주교 집안인 것이 탄로되어 서울을 떠나야 했는데 이 때 최경환은 과천(果川)의 수리산 뒤뜸이로 피신하였다. 여기서 그는 산지를 개간하며 연명해 나아갔다. 최양업은 16살이 되는 해에 이 곳 수리산에서 신학생으로 선발되었다.

1836년초 입국에 성공한 모방(Maubant, 羅伯多祿) 신부는 즉시 조선인 성직자 양성을 위해 신학생 선발에 착수했는데, 맨 먼저 최양업이 발탁되었고, 이어 최방제(崔方濟)와 김대건이 발탁되었다. 최양업 등 세 소년은 서울의 모방 신부 곁에서 라틴어를 배우며 출발을 기다렸다. 왜냐하면 모방 신부는 그들을 국외로 내보내어 성직자로 양성할 계획이었기 때문이다.

세 소년은 마침내 그해 12월 3일 마카오로 가기 위해 의주(義州)를 향해 서울을 떠났다. 이들은 출발에 앞서 그 전날 모방 신부 앞에서 소명(召命)에 충실하고 장상들에게 순종할 것을 선서하였다. 정하상(丁夏祥), 조신철(趙信喆) 등 유지 교우들이 그들을 동행했는데 이들은 세 소년을 변문(邊門)까지 인도하고 거기서 새 선교사를 맞아들이게 되어 있었다. 일행이 12월 28일 변문에 도착한 후, 세 소년은 중국인 안내원을 따라 중국 대륙을 횡단, 이듬해 6월 7일 목적지인 마카오에 무사히 도착하였다.

마카오 주재 파리 외방전교회 극동 경리부 책임자 르그레주아(Legregeois) 신부는 경리부 안에 임시로 조선신학교를 세워 조선인 신학생 3명을 교육하기로 결정하였다. 이에 따라 르그레주아 신부 책임 하에 경리부 차장 리부아(Libois) 신부가 주로 그들의 교육을 담당하였다. 그러나 후에 조선 선교사로 부임한 데플레슈, 메스트르(Maistre)와 베르뇌(Berneux) 신부 등 선교사들이 마카오에 체류하는 기회에 그들의 교육을 돕기도 하였다. 최양업과 김대건은 아편전쟁을 전후해 현지에서 일어난 민란(民亂)으로 인하여 두 번이나 마닐라로 피난해야 했고, 또 최방제와 1년여 만에 사별(死別)하는 등 그들의 유학생활이 순탄하지만은 않았으나 그래도 1842년까지 공부를 계속할 수 있었다.

1842년 그들은 아직 수학 중이었음에도 불구하고 갑자기 귀국길에 오르게 되었다. 왜냐하면 세실(Cecille) 함장이 마카오의 경리부를 찾아와 조선원정계획을 알리면서 조선인 신학생 1명을 통역으로 동행시켜줄 것을 요청했고, 경리부장 리부아 신부는(그간 르그레주아 신부는 파리본부로 전임되었다) 벌써 몇 년째 조선교회와 소식이 끊겨져 있었으므로 세실의 요청을 하느님의 섭리처럼 생각하고 쾌락했기 때문이다. 아편전쟁의 종말이 가까워지자 프랑스 정부는 중국에서 어떤 이득을 얻어 보려는 심산에서 군함 2척, 즉 에리곤호와 파브리트호를 파견했었는데 세실은 에리곤호의 함장이었다. 리브와 신부는 건강이 약한 김대건을 메스트르 신부와 같이 먼저 에리곤호에 태워 보냈다(2월 15일). 한편 최양업은 파브리트호로 떠나게 되어 있었는데 입항(入港)이 늦어져 7월 17일에야 요동(遼東)교구 선교사 브뤼니에르(Bruniere) 신부와 같이 마카오를 출항하였다.

최양업은 소팔자가(小八家子) 교우촌에서 신학공부를 계속하였다. 한편 김대건은 입국에 실패했으나 그간의 조선교회 소식을 자세히 들을 수 있었다. 무엇보다도 1839년 기해박해로 3명의 선교사를 위시하여 그의 부친 최양업의 부모 등이 순교한 소식에 접하게 되었고, 이 소식을 전해들은 최양업은 오히려 그들의 순교에 동참하지 못한 것을 부끄러워하며, 피로 물든 조국땅을 오히려 희망적이라고 하였다.

그러는 동안 페레올 신부가 제3대 조선교구장으로 임명되었고, 1843년 12월 31일 개주(蓋州)에서 주교성성식을 갖게 되었다. 성성식에 참석한 후 최양업은 메스트르 신부와 같이 소팔가자로 돌아왔고, 얼마 뒤 페레올 주교와 김대건도 소팔가자로 돌아왔다. 그간 김대건은 다시 한 번 훈춘을 통해 입국을 시도했었다.

최양업은 1845년 한 해를 기다림 가운데 허송한 뒤 1846년 초에 메스트르 신부와 같이 두만강 쪽을 통해 처음으로 입국을 시도했으나 실패하였다. 그 뒤 최양업은 요동교구의 베르뇌 신부의 사목활동을 도우며 1846년을 보냈다. 1846년 말 변문을 통해 두 번째 입국을 시도했으나 또 실패하였다. 이 때 그는 김대건 신부가 순교한 소식을 들었다. 이제 최양업은 육로(陸路)로의 입국을 단념하고 해로(海路)로의 입국을 시도하고자 홍콩의 경리부로 갔다(그간 경리부는 마카오에서 홍콩으로 이전되어 있었다).

라피에르 함장은 메스트르 신부, 최양업 등과 같이 군함 2척을 이끌고 1847년 7월 28일 마카오를 떠났다. 그러나 두 군함은 고군산도(古群山島)에 이르러 완전히 난파하였다. 상해로부터 구조선이 도착하기를 기다리는 동안 최양업은 육지로 잠입하고자 온갖 노력을 기울였으나 성공하지 못하고 부득이 구조선을 타고 상해로 돌아와야 하였다. 난파된 군함의 잔해(殘骸)를 거두러 갈 것이 거의 확실시 되었으므로 그 기회를 기다렸으나 그것도 프랑스의 국내 사정으로 실현되지 못하였다. 그러는 동안 1848년도 지나가 버렸다.

1849년 최양업은 백령도를 통해 입국을 네 번째로 시도했으나 또 실패하였다. 상해로 돌아온 그는 4월 15일 강남교구장 마레스카(Maresca) 주교로부터 숙원인 사제품을 받고 동료 김대건에 이어 두 번째 한국인 신부가 되었다. 최 신부는 다시 육로 입국을 시도하고자 5월 요동으로 떠났다. 연말을 기다리며 7개월 동안 베르뇌 부주교를 도우며 사목경험을 쌓았다. 12월 변문으로 떠났고, 이번에는 입국에 성공했다. 그러나 메스트르 신부와 같이 입국하지는 못했다. 실로 입국 길에 오른 지 7년 6개월, 입국의 시도를 거듭하기 다섯 번만의 성공이었다.