Illegal Immigrant is a common problem between Indonesia and Australia. However, in handling the problem in sea border, Indonesia take a humanitarian approach while Australia take security approach through Operation Sovereign Border that had resulted to diplomatic confrontation. Therefore, this study focus on analyzing synergy of the two countries in dealing with illegal immigrant in sea border area. This study uses national security, migration as security issue to analyze national interest. Cooperative security, defense diplomacy, synergy concept and naval diplomacy theory to analyze defense diplomacy implementation as a whole. The approach of this study is qualitative method through data collection processed by software NVivo which are beneficial for coding, triangulation, and finding relations among interviewees while Soft System Methodology used as data analysis technique consist of seven steps that are very comprehensive in explaining the whole study. The results of this study showed the two countries have not synergized yet. Indonesia and Australia have common non-traditional security interests and different traditional security interests because Indonesia has a territorial importance base opposed to Australian immigration interests. Indonesia and Australia have been doing bilateral defense diplomacy through 2 + 2 Dialogue, Defense Ministers Meeting and Navy to Navy Talk but have not produced a concrete solution, therefore sharing responsibility and Confidence Building Measures have not been achieved. Thus, naval diplomacy is required to support defense diplomacy through coordinated patrols that Standard Operating Procedure and Standard Exercise Procedure must be formulated in order to achieve interests of both countries.