Le parti est fondé le , en vue de prendre part aux élections législatives de novembre. À l'instar de partis travaillistes dans d'autres pays, dont le Parti travailliste au Royaume-Uni ou le Parti travailliste australien, ce parti a pour origine et fondements des mouvements syndicaux. Le parti est établi conjointement par onze organisations syndicales professionnelles, à l'initiative d'Ephraim Kalsakau, président du Syndicat des travailleurs municipaux du Vanuatu. Le parti présente quatre candidats aux élections de 1987, mais sans succès. Il n'a pas non plus d'élus au cours des élections suivantes, mais en 2005 Joshua Kalsakau, député et Ministre du Commerce autochtone, quitte l'Association de la communauté nationale et rejoint le Parti travailliste, offrant à ce dernier son premier député et ministre. Joshua Kalsakau est réélu député en 2008, sous l'étiquette travailliste, demeurant le seul député de ce parti. Il est nommé très brièvement Ministre de la Justice dans le gouvernement de coalition du nouveau Premier ministreEdward Natapei, avant de perdre son poste lors d'un remaniement une semaine plus tard, visant à accorder des ministères à de nouveaux alliés du gouvernement[2],[3],[4]. En et en , les députés Ioane Simon et Samson Samsen rejoignent le Parti travailliste, quittant respectivement Nagriamel et le Parti républicain. Pour la première fois, les Travaillistes ont ainsi trois députés[5].
Le parti fait campagne en faveur d'une juste répartition des ressources, et du commerce équitable. Il s'oppose à toute privatisation des services de santé et d'éducation[2].