Mit fünf Jahren musste Martins mitansehen, wie sein Vater bei politischen Unruhen getötet wurde. Als er 17 war schloss er sich der osttimoresischen pro-Unabhängigkeits-Studentenbewegung RENETIL von Fernando de Araújo an.[1] Am 19. November 1991 nahm Martins an einer Demonstration in Jakarta teil, gegen das Santa-Cruz-Massaker, sieben Tage zuvor in Dili. Daraufhin wurde er bis zum 4. Dezember im Polda Metro Jaya Gefängnis inhaftiert. 1992 war er Gründungsmitglied der Independent Student Movement Pro Timor-Leste Independence in Bandung. 1994 wurde Martins erneut von den Indonesiern festgenommen und kam in ein Militärgefängnis in Bandung. Ihm gelang aber mit drei Mitgefangenen die Flucht und hielt sich drei Monate in Westjava versteckt. 1995 schoss Martins sich der Brigada Negra an.[2]
Zwischen 1995 und 1998 engagierte sich Martins auch gegen die Kinderarbeit in Indonesien. Seit Juli 1995 war er Mitglied der indonesischen Arbeiterbewegung. Führend beteiligt war Martins an den Studentenprotesten, die 1998 schließlich zur Abdankung des indonesischen Diktators Suharto führten. Martins war zwischenzeitlich eingesperrt worden und hatte seinen Studienplatz und Stipendium verloren. Daraufhin half er als Mediziner den Widerstandskämpfern der FALINTIL in Osttimor. Am 9. August 1998 wurde Martins Gesundheits- und medizinischer Koordinator für die Region IV in der Unabhängigkeitsbewegung. Ab dem 10. September war er für ganz Osttimor zuständig. Einer seiner Patienten in dieser Zeit war der Guerillaführer Taur Matan Ruak, der spätere Staatspräsident Osttimors. 1998 erhielt Martins seinen MD.[1][2]
Während der UN-Verwaltung Osttimors (1999–2002) war Martins Mitglied der Interim Health Authority aus der später das Gesundheitsministerium hervorging. Zu dieser Zeit war er Generalsekretär der demokratisch-sozialistischen Partido Trabalhista (März 2000–Juli 2007). Seine medizinische Ausbildung erhielt er in Bandung (Indonesien) und in Australien. 2003 immatrikulierte Martins an der Menzies School of Health Research der Charles Darwin University im Northern Territory (Australien). Im Rahmen seines Studiums arbeitete er an einem Programm zur Bekämpfung der Tuberkulose in Osttimor, womit er Erfahrungen in klinischer Medizin, öffentliche Gesundheit und humanitäre Arbeit sammelte.[1] Seine Forschungen richteten sich auf das Nationale Tuberkulosekontrollprogramm, dessen Gründer er war. Martins Ergebnisse sind von Interesse für die Tuberkulosebekämpfung weltweit. Im Juni 2007 graduierte Martins als erster Osttimorese als Arzt für Allgemeinmedizin mit Ph.D. Die Ausbildung wurde durch die Weltgesundheitsorganisation (WHO) finanziert. Bis zu seiner Berufung im April 2007 als Gesundheitsminister arbeitete Martins an einer Forschungsstelle als Post-Doc an der School of Public Health and Community Medicine der medizinischen Fakultät von der University of New South Wales in Sydney und ehrenamtlich als Dozent an der Fakultät für das Gesundheitswesen der Universidade da Paz (UNPAZ) in Dili (Osttimor). Parallel zu seinem Ministerposten hatte Martins auch das Amt des Präsidenten der Nationalen HIV/AIDS-Kommission inne.[2]
Nach den Parlamentswahlen in Osttimor 2012 übergab Martins am 8. August 2012 den Ministerposten an seinen Nachfolger Sérgio Lobo. Ende 2013 war Martins ist Direktor für Aufbaustudium und Forschung an der Universidade Nasionál Timór Lorosa'e (UNTL) und bildet neue osttimoresische Mediziner aus.[1] Inzwischen ist er Professor der Fakultät für das Gesundheitswesen an der UNPAZ, Gastprofessor der Fakultät für Medizin und Gesundheitswissenschaft an der UNTL und außerordentlicher Professor an der School of Public Health, School of Medicine.[2]
Von 2014 bis 2015 hatte er einen Jahresvertrag beim Sekretäriat der g7+-Staaten als Senior Researcher zur Koordinierung und Erforschung von Natürlichen Ressourcen, Öffentlichkeitsarbeit, der Effektivität von Hilfsmaßnahmen und Erfolge der Mitgliedsstaaten bei der Umsetzung der Millenniumsziele der Vereinten Nationen.[2]
2013 gründete Nélson Martins eine neue politische Partei,[3] die Movimentu Libertasaun ba Povu Maubere (MLPM). Am 16. November 2013 wurde er zum Präsidenten der Partei gewählt.[4]