Penelitian ini memfokuskan perhatian pada Strategi Diplomasi Indonesia dalam meningkatkan Perlindungan Tenaga Kerja Indonesia asal NTT di Malaysia. TKI yang bekerja secara legal dengan dokumen yang tepat dan izin kerja yang dikirim oleh badan penyalur yang sah akan terlindung hak-haknya dalam bekerja. Sebaliknya TKI yang tidak memiliki dokumen (undocumented) dan ilegal akan rentan terhadap masalah eksploitasi dan manipulasi. Karena itu upaya diplomasi perlindungan TKI, yang mencakup tiga langkah :Pencegahan, Deteksi dini dan Perlindungan secara cepat dan tepat sangat relevan untuk terus dilaksanakan. Berdasarkan data statistik BNP2TKI tahun 2015, Provinsi NTT menempati urutan ke 11 sebagai provinsi yang banyak mengirim tenaga kerja ke luar negeri khususnya ke Malaysia. Dari sebaran TKI asal NTT yang berada di luar negeri antara tahun 2013-2015, terdapat 11.345 orang NTT yang bekerja di Malaysia. Umumnya TKI asal NTT memiliki dokumen tatapi tidak mempersiapkan diri dengan pengetahuan tentang aturan bekerja di luar negeri serta ketrampilan dasar yang dibutuhkan sehingga banyak diantara mereka mengalami masalah dan kesulitan saat bekerja karena itu diplomasi perlindungan terhadap TKI asal NTT sangat diperlukan.

Kata Kunci : Strategi Diplomasi, Perlindungan TKI, TKI di Malaysia, Undang-Undang nomor 39 tahun 2004.