Sau hàng mấy giờ đồng hồ thăm dò họ chẳng thu lượm được gì. Họ bắt đầu tin là ông không còn trung thành với Khơme Đỏ. Hình như họ đã tin chắc sự rời bỏ hàng ngũ của ông là quyết đinh cuối cùng không thể thay đổi được nữa, họ tin ông đã cắt hết mọi con đường có thể trở về Campuchia và ông sẽ bị giết nếu bị trả về.
Sau khi trải qua 22 ngày trong tù ở Sông Bé, ông còn bị giam thêm 3 tháng nữa trong tỉnh này. Rồi sau đó ông xin được tị nạn chính trị.
Năm người Campuchia ấy được di chuyển tới một trại giam khác trong khi vấn đề xin tị nạn chính trị đang được cứu xét. Cho tới khi quy chế này được ban bố thì họ vẫn bị giam giữ.
Tuy vậy, có được sự bù đắp cho quá trình ấy. Hun Sen được cung cấp chi phí sinh hoạt mỗi ngày 21.000 đồng, bằng với các khẩu phần ăn của một Bộ trưởng của chính phủ Việt Nam. Số tiền ấy được chi vào mỗi cuối tháng, đó là tín hiệu cho thấy ông dần dần đã chinh phục được lòng tin của những người Việt Nam, họ đã chuyển biên dần từ những người coi tù và điều tra thành những người chủ nhà và cuối cùng là bạn đồng minh.
Ông kể “ Không những tôi đủ ăn, đủ thuốc hút mà tôi còn có một ít tiền để dằn túi “.
Là một người đàn ông có khẩu vị thanh đạm, Hun Sen không thích cách nấu nướng ngoại lai và thích nhất cách ăn giản dị của bữa cơm với cá. Đam mê của ông là thuốc lá. Khi không được thỏa mãn cái thú này ông trở nên bứt rứt khó chịu. Trong suốt thời gian qua các nhà tù khác nhau ở Việt Nam, ông hút thuốc lá Vàm Campuchiaỏ và đôi khi vấn thuốc rê hút.
Ông nói “ Tôi khó lòng bỏ được hút thuốc. Trong những giai đoạn khó khăn thậm chí tôi hút lá đu đủ. Trong nhà giam, tôi để dành các mẩu thuốc và dùng chúng để quấn thành điếu thuốc mới. Theo kiểu suy nghĩ của tôi thì mình luôn luôn cố gắng tìm cái gì để hút trong các giai đoạn khan hiếm, khó tìm, vì vậy tại sao phải bỏ hút khi mình có thể dễ dàng có được?”.
Sau hàng tháng sống trong bồn chồn lo lắng, cuối cùng ông đã vượt qua được. Do yêu cầu của ông xin tị nạn chính trị, ông đã được tạo cho cơ hội hiếm hoi gặp Đại tướng Văn Tiến Dũng, Tổng tham mưu trưởng Quân đội Việt Nam và các sĩ quan quân đội cao cấp khác tại thành phố Hồ Chí Minh vào ngày 30 tháng 9 năm 1977. Đó là ngày tháng hết sức ý nghĩa. Vào chính ngày đó, Pol Pot đi thăm lại Trung Quốc, sau chuyến thăm ban đầu sang Bắc Kinh vào năm 1966. Khi Pol Pot phát triển mối quan hệ thân hữu hơn với Trung Quốc, thì Hun Sen được Hà Nội bao bọc. Việt Nam cần một liên minh Campuchia để đối trọng với trục Trung Quốc – Khơme Đỏ đe dọa tới Việt Nam.
Các cuộc nói chuyện giữa Đại tướng Dũng, người sau này đã lên làm Bộ trưởng Quốc phòng và Hun Sen đã lóe lên tia sáng đầu tiên trong tầm nhìn mà ông đã thấy được khả năng giải phóng đất nước của mình. Họ nói chuyện trung thực và ông đã thẳng thắn cởi mở ý định tìm kiếm sự giúp đỡ. Nhưng ông cảm thấy thất vọng bởi câu trả lời của ông đại tướng.
Hun Sen kể “ Họ cho chúng tôi biết là họ không thể giúp chúng tôi, và họ sẽ cố gắng giải quyết vấn đề với Campuchia dân chủ (tên gọi chính thức của chính phủ Khơme Đỏ ). Một số tướng tá Việt Nam đã đề nghị tôi nên tới Thái Lan (để tìm kiếm sự trợ giúp). Tôi nói với họ tôi không thể từ bỏ dân tộc của mình. Nếu họ không thể giúp tôi, tôi nói ‘ Hãy cho tôi một số vũ khí để tôi sẽ trở về Campuchia và hy sinh cho dân tộc mình’ ”.
Không phải ông hoàn toàn không tìm kiếm được gì. Ông đã được chấp nhận nơi xin tị nạn, nhưng chính phủ Việt Nam từ chối ủng hộ quân sự cho ông, vì họ không muốn can dự vào quá nhiều. Nhưng ông không đến Việt Nam để tìm kiếm nơi tị nạn chính trị; ông muốn họ giúp giải phóng đất nước của ông.
Ông kể “ Khi yêu cầu sự trợ giúp của họ, tôi đã bị từ chối. Việt Nam cho biết nếu họ đồng ý yêu cầu của tôi xin giúp đỡ, họ sẽ bị coi là can thiệp vào công việc nội bộ của Campuchia dân chủ. Khi ấy chính phủ Việt Nam sẽ cố gắng đàm phán với Campuchia dân chủ để làm dịu các căng thẳng quân sự trên biên giới chung “.
Hun Sen không dễ dàng thuyết phục được phía Việt Nam giúp ông giải phóng Campuchia khỏi chế độ diệt chủng của Khơme Đỏ bằng cách ủng hộ ít nhất 50.000 quân thiện chiến. Xét cho cùng, từ trước tới nay, Việt Nam đã là một liên minh đáng tin cậy của Khơme Đỏ. Hà Nội đã huấn luyện các lực lượng Pol Pot và những ngày đầu của phong trào kháng chiến và hai bên đã chỉ đạo các hoạt động phối hợp chung chống lại lực lượng Cộng hòa của Lon Nol, quân lực miền Nam Việt Nam và quân đội Mỹ.
Hun Sen kể “Việt Nam luôn luôn tôn trọng sự độc lập và chủ quyền của Campuchia, các vị lãnh đạo của Việt Nam đã từ chối lời thỉnh cầu giúp đỡ của tôi và nói điều đó có thể làm phương hại đến mối quan hệ giữa hai nước “.
Thay vào đó, họ đề nghị ông đi sang Thái Lan, sau đó đi sang nước thứ ba. Hun Sen nói dứt khoát với họ là ông sẽ không đi sang Thái Lan.
Hun Sen có được rất nhiều thuận lợi từ sự thay đổi diễn ra nhanh trong các liên minh khu vực. Ông đã thấy những ngày thanh bình giữa Khơme Đỏ và Việt Nam đang nhanh chóng đến hồi kết thúc khi Pol Pot ngày càng thân thiết hơn với Trung Quốc và thù địch với các bạn bè ban đầu, những người Việt Nam.
Hun Sen nói, một cơ hội “vàng” đã xuất hiện khi Pol Pot tấn công Việt Nam vào năm 1977. Thái độ gây hấn của Pol Pot đã đánh dấu thời kỳ bắt đầu thay đổi chính sách của Việt Nam. Hà Nội không còn giữ lập trường không can thiệp của họ nữa và tính đến hành động trả đũa.
Hun Sen kể “ Nếu Pol Pot không tấn công Việt Nam, tôi nghĩ chúng tôi sẽ không có được sự ủng hộ của Việt Nam để lật đổ chế độ Khơme Đỏ. Pol Pot đã vướng phải sai lầm là đã giết người dân của chính ông ta (kể cả những người gốc Việt) và phát động các cuộc tấn công vào Việt Nam “.
Các sự kiện chính trị bắt đầu nhanh chóng diễn ra theo chiều hướng có lợi cho Hun Sen. Sau khi bị Pol Pot tấn công, Việt Nam cảm thấy bị xúc phạm và xét lại thái độ trung lập của họ đối với người láng giềng bặm trợn của họ. Khi Pol Pot tái bố trí các lực lượng của ông ta từ tây nam Campuchia tới phía đông Campuchia để sẵn sàng tấn công Việt Nam, điều đó đã buộc một số lớn người dân Campuchia trốn sang Việt Nam.
Ông kể “ Đó là một cơ hội bằng vàng cho tôi. Đến khi ấy Việt Nam đã quyết định giúp Campuchia. Đó là cơ hội cho chúng tôi tuyển mộ các lực lượng vũ trang của mình từ những người lánh nạ Campuchia đã chạy sang Việt Nam. Chính bản thân tôi đã không thể thuyết phục được Việt Nam. Nhưng khi Pol Pot tấn công thì Việt Nam phải trả đũa. Họ cảm thấy bị xúc phạm và đã quyết định giúp chúng tôi “.
Hun Sen kể “ Các nhà lãnh đạo Việt Nam đã bắt đầu tin vào lời dự đoán của tôi là Pol Pot đã có kế hoạch tấn công Việt Nam. Khi ấy ngày càng có nhiều người trốn sang Việt Nam. Việt Nam đã tin chắc là có nguy cơ nghiêm trọng đe dọa tới an ninh của họ. Lúc đó các nhà lãnh đạo Việt Nam đã cho gọi tôi tới sở chỉ huy của họ và yêu cầu tôi xác định vị trí rõ ràng các tọa độ (bên trong Campuchia ) mà họ sẽ tấn công”.
Nổi giận bởi các cuộc tấn công dã man do Pol Pot phát động, các lực lượng của ông ta đã đốt nhà cửa làng mạc của người Việt và chiếm một số nơi ở tỉnh Tây Ninh vào tháng 9, bộ đội Việt Nam chống trả lại các lực lượng Khơme Đỏ ở Svay Rieng, Prey Veng, Kompong Cham, Kratie và một số khu vực của Kandal. Bằng cách tự vệ, họ đã tấn công Campuchia ở các địa điểm vào sâu từ 30 tới 70 kilômét.
Hun Sen kể “ Đó là cơ hội cho tôi trở lại Campuchia và cố tìm kiếm vợ mình đã di tản sang một nơi khác “.
Khi những người cầm đầu Khơme Đỏ càng liều lĩnh hơn phát động các cuộc tấn công vào sâu trong tỉnh Tây Ninh của Việt Nam vào tháng giêng và tháng hai năm 1978, bộ đội Việt Nam đã đánh trả lại bằng hỏa lực kinh hoàng. Một hãng thông tấn của Việt Nam cho biết Pol Pot đã nã pháo 130 ly vào Tây Ninh, một thị xã có đông người lánh nạn Campuchia bị kẹt lại, cách Sài Gòn 90 kilômét về hướng bắc, đã giết chết hoặc gây thương tích cho 30 thường dân. Đồng thời các sư đoàn Việt Nam được yểm trợ bằng xe tăng, pháo binh và máy bay đã thâm nhập vào sâu Campuchia 30 kilômét dọc biên giới ở kilômét 700, từ phía bắc Ratanakiri tới phía nam Svay Rieng. Đái phát thanh Phnom Penh đã đưa ra lời kêu gọi của Khieu Samphan, người đứng đầu nhà nước với quân đội và thường dân hãy tự bảo vệ chống lại “tất cả các kẻ thù” xâm lăng Campuchia để cướp phá vụ thu hoạch lúa. Samphan kết tội các lực lượng Việt Nam đã phá hủy các nông trường cao su, đốt rừng và nhà cửa, bắn bừa bãi vào dân chúng Campuchia. Chính quyền Campuchia đã cắt đứt các mối quan hệ với Việt Nam cũng như hủy bỏ toàn bộ các liên đới về đường hàng không.
Hun Sen đã thúc giục các nhà lãnh đạo Việt Nam đóng vai trò chủ động hơn nữa, nhưng ông đã bị thất vọng.
Ông kể “ Tôi cảm thấy rất bực mình vì các lãnh đạo Việt Nam, vì thậm chí ngay sau khi tấn công Campuchia, họ đã quyết định rút quân. Họ không tạo cho chúng tôi nơi đồn trú an toàn ở Campuchia để chúng tôi có thể xây dựng các lực lượng của mình. Họ đã rút quân sau khi mở ra các cuộc tấn công trong thời gian ngắn để tự bảo vệ họ. Chúng tôi không có được các lực lượng tự vệ riêng. Nhưng tôi rất biết ơn họ đã cho phép dân chúng Campuchia di tản sang các khu vực của họ khi đang bị tấn công và đến sống ở Việt Nam. Điều đó đã tạo cho tôi cơ hội tuyển mộ lính cho các lực lượng của mình. Bằng cách này chúng tôi đã có thể xây dựng được 28 tiểu đoàn. Nhiều tướng một sao và hai sao hiện đang công tác đã được tôi tuyển mộ vào năm 1977 “.
Chính sách tuyển mộ của ông đã đem lại được lợi ích. Với việc tuyển chọn cẩn thận các tướng lĩnh, đại tá và thiếu tá nòng cốt, Hun Sen đã bắt đầu xây dựng được cơ sở ủng hộ của ông ngay từ đầu năm 1977 và vào thập niên 1990, các thành viên mới của ông đã kiểm soát toàn bộ đất nước qua một mạng lưới rộng lớn vốn vẫn còn trung thành với vị lãnh đạo tối cao của họ.
Khi thành lập lực lượng chiến đấu trong số những người lánh nạn tùy theo năng lực, ông đã nổi lên như người lãnh đạo đứng đầu của họ.
Ông kể “ Họ gọi tôi là Tư lệnh miền Đông sông Mê kông. Có nhiều người còn già hơn tôi, nhưng họ đã trao cho tôi vai trò lãnh đạo. Các tiểu đoàn chúng tôi xây dựng lên để chống lại Pol Pot, chủ yếu họ tin tưởng các lực lượng của tôi “.
Khi các tướng lĩnh Việt Nam bố trí các kế hoạch giúp ông, ông biết phương Tây đang theo dõi sát sự phát triển các lực lượng giải phóng Campuchia.
Trong thời gian còn tị nạn chính trị, Hun Sen đã dần phát triển mối quan hệ bền vững với các cán bộ chỉ huy quân sự cao cấp của Việt Nam. Sau khi gặp Tướng Văn Tiến Dũng, ông đã được giới thiệu với Tướng Trần Văn Trà, đang là Tư lệnh quân khu 7, bao gồm khu vực thành phố Hồ Chí Minh, cũng như các Phó Tư lệnh quân khu này. Các mối quan hệ đã chứng tỏ là vô giá.
Một trong các mối quan hệ có lợi nhất mà Hun Sen đã phát triển được là với Tướng Lê Đức Anh, người đã trở thành một trong những nhân vật quan trọng nhất trong việc thiết lập tổ chức quân của Việt Nam. Vào đầu thập niên 1990, tướng Anh đã trở thành Chủ tịch nước. Khi Hun Sen trốn sang Việt Nam, Tướng Anh là Tư lệnh quân khu 9. Sau này, khi Tướng Anh được chỉ định làm Tư lệnh quân khu 7, Hun Sen đã gặp ông ở một bệnh viện dành cho các quan chức trung và cao cấp.
Hun Sen kể “ Lúc ấy tôi thường hay bị bệnh phải nhập viện. Tôi là người trẻ nhất được phép ở tầng 4 của bệnh viện vốn dành cho các tướng lĩnh. Tôi đã phải cải trang thành một người ở Lào”.
Tại bệnh viện, gần như tất cả mọi người đều không tin một người trẻ như thế có thể là một sĩ quan cấp cao. Các bạn bè Việt Nam của ông gọi ông bằng danh tánh mới vì thế ông không gây ra sự chú ý hoặc tăng thêm sự nghi ngờ.
Hun Sen kể “ Họ đặt cho tôi cái tên là Mãi Phúc ( có nghĩa là hạnh phúc mãi ), 26 tuổi, cán bộ cao cấp quân khu X. Chẳng ai biết quân khu X ở đâu. Những người ở trong bệnh viện có điều nghi ngờ, vì bình thường ở Việt Nam chỉ những người 60 tuổi trở nên mới có thể được xem là cán bộ cao cấp. Những người ở tầng 4 biết cấp bậc của tôi, nhưng khi tôi được đưa tới phòng chụp X quang, những người ở đó thắc mắc ‘Cán bộ cao cấp sao chỉ mới 26 tuổi, ông ta ở đâu đến?’ “.
Ở đó, ông đã trở thành thân quen với Tướng Anh.
Ông kể “ Ông ta giúp tôi rất nhiều từ các nguồn khí tài của quân khu 7 để xây dựng các lực lượng vũ trang Campuchia. Ông còn cử một vài tướng tá tới giúp tôi hoạt động. Ông là nhân vật chính đã bảo đảm sự lật đổ Khơme Đỏ thành công “.
Đến lúc ấy, các nhà lãnh đạo Việt Nam đã thận trọng, thậm chí có phần miễn cưỡng về việc họ phải dành cho Hun Sen và nhóm người cách mạng của ông bao nhiêu sự trợ giúp nữa.
Ông kể “ Các lãnh đạo Việt Nam đã từ chối tạo cho chúng tôi sự trợ giúp chính trị. Nhưng họ giúp chúng tôi về mặt tài chính. Họ cung cấp cho chúng tôi vũ khí và giúp huấn luyện, còn công việc về vai trò lãnh đạo chính trị và giáo dục họ để mặc cho chúng tôi. Do đó, tôi đã biết cách phải viết các tài liệu chính thức như thế nào ở tuổi mới 25. Tôi đã viết các bài học cho các sĩ quan Campuchia và chính mình đứng giảng “.
Bằng trình độ được nâng dần, ông đã xây dựng được các lực lượng của mình từ con số không.