Guterres adalah anggota Komite Sentral partai berkuasa terdahulu Fretilin. Ia menjabat sebagai duta besar pemerintah Timor Leste yang tidak diakui untuk Angola, Mozambik, dan Perserikatan Bangsa-Bangsa. Ketika negaranya merdeka pada Mei 2002, ia diangkat sebagai duta besar Timor Leste pertama untuk A.S. dan merangkap PBB.
Pada tahun 2006, setelah krisis politik internal di Timor Leste, Guterres berusaha mengambil alih kepemimpinan Fretilin dari Mari Alkatiri, Sekretaris Jenderal partai tersebut, tetapi Alkatiri menang dalam kongres nasional Fretilin. Guterres diangkat menjadi menteri luar negeri di bawah Perdana Menteri José Ramos-Horta di akhir tahun tersebut,[3] menjabat di posisi tersebut hingga Mei 2007.
Pendukung Guterres, yang terdiri dari faksi sempalan Fretilin bernama "Mudança" (berarti "reformasi"), mendukung saingan utama Fretilin, Kongres Rekonstruksi Timor Nasional (CNRT) yang dipimpin mantan presiden Xanana Gusmão, dalam Pemilihan umum parlemen Juni 2007. Meskipun demikian, faksi Guterres menolak meninggalkan Fretilin, dan Alkatiri mengancam akan mengambil tindakan hukum.[3]
Meskipun Fretilin memenangkan suara terbanyak dalam pemilihan umum parlemen, CNRT membentuk koalisi dengan partai-partai lain untuk mempertahankan mayoritas di parlemen. Dalam pemerintahan yang dilantik di bawah Gusmão, yang kemudian menjadi Perdana Menteri, pada 8 Agustus 2007, Guterres menjadi Wakil Perdana Menteri.[3]
Jose Luis Guterres, yang juga dikenal sebagai "LUGU", bersama kelompoknya seperti Jorge Teme (Sekretaris Negara Enklave Oecusse saat ini), berupaya mendaftarkan FRETILIN-Mudança sebagai partai politik yang memisahkan diri dari Fretilin, tetapi kemudian ditolak oleh Pengadilan Tinggi Timor-Leste karena atribut politiknya: bahkan nama partai tersebut mirip dengan partai politik yang sudah ada, Fretilin. Beberapa hari kemudian, setelah diberi kesempatan untuk melakukan modifikasi agar dapat didaftarkan secara resmi, mereka mengubah FRETILIN-Mudança menjadi FRENTI-Mudança. Partai tersebut kemudian disetujui oleh Pengadilan Tinggi Timor-Leste.
Dalam Pemilihan umum parlemen 2012, partai ini memenangkan dua kursi di parlemen. Guterres menyerahkan kursinya untuk menjadi menteri luar negeri dalam koalisi pemerintahan baru yang dipimpin oleh Xanana Gusmão, dan tetap menjabat hingga tahun 2015, ketika ia kembali ke parlemen.
