Po odejściu z rządu w 1998 pracował jako prawnik. W latach 1998–1999 był specjalnym przedstawicielem sekretarza wykonawczego Wspólnoty Państw Portugalskojęzycznych, monitorując konflikt polityczno-wojskowy w Gwinei Bissau. W 2000 wystąpił z szeregów Niezależnej Akcji Demokratycznej. W lipcu 2000 prezydent Fradique de Menezes mianował go ambasadorem w Lizbonie, którym pozostał do marca 2002.
Po wyborach parlamentarnych z 3 marca 2002, w których MLSTP-PSD zdobyła jeden mandat więcej niż prezydencki Ruch Demokratyczny Siły na rzecz Zmiany-Partia Liberalna, negocjacje zmierzające do wyłonienia nowej koalicji zakończyły się brakiem porozumienia. W tej sytuacji prezydent de Menezes 28 marca 2002 mianował niezależnego Costę na stanowisko szefa rządu. Utworzył on "rząd jedności narodowej", popierany przez wszystkie trzy partie i koalicje wyborcze zasiadające w parlamencie (MLSTP-PSD, koalicja Ruchu Demokratycznego Siły na rzecz Zmiany-Partii Liberalnej i Partii Konwergencji Demokratycznej, koalicja Uê Kédadji na czele z ADI). Rząd, liczący 11 ministrów, składał się głównie z bezpartyjnych specjalistów i technokratów. Gabinet Costy przetrwał pół roku. 27 września 2002 został zdymisjonowany przez prezydenta na tle sporu z armią w sprawie awansu na stopień podpułkownika urzędującego oraz byłego ministra obrony.