Patrick Sullivan, 25 år, före detta fransk utländsk legionär och medlem av den republikanska splittergruppen, Irish People's Liberation Organisation, knivhöggs till döds i februari 1992.
En man i västra Belfast dömdes senare för dråp.
Hans syster och bror träffade polisen i Belfast på fredagsmorgonen.
Mr Sullivan dödades efter att ha konfronterat någon han misstänkte för antisocialt beteende i Divis-området.
Han knivhöggs i nacke och rygg och dog av sina skador.
Familjen har alltid trott att mer än en angripare var inblandad och hävdar en obduktionsundersökning som de nyligen har fått tillbaka sitt påstående.
Patricks syster, Margaret, och hans bror, Seamus, tillsammans med deras advokat, Padraig Ómuirigh, träffade detektiver för en timme lång möte på fredag.
Familjen skulle inte avslöja vad som hade sagts, men deras advokat sade att de hoppades att den nya information de hade skulle vara tillräckligt för att åter öppna fallet.
"Vi hade ett konstruktivt möte med polisen och hoppas kunna ge dem ytterligare information", sade Ómuirigh.
"Familjen har också lämnat in ett klagomål till polisombudsmannen om normerna i den ursprungliga utredningen och vi har också ett möte med ombudsmannen under de kommande veckorna."
När man bad om en kommentar till mötet, sade en talesman för polisen: "Vi kan bekräfta att lokalpolisen träffade medlemmar av familjen Sullivan idag."
Polisombudsmannen sade: " Vi har fått ett klagomål om polisutredningen av mordet på Patrick Sullivan i Belfast 1992.
"Vi undersöker klagomålet och utredarna ska träffa mr Sullivans familj den 30 augusti."
Familjen till en västra Belfast man som dödades för 20 år sedan har krävt en ny utredning om hans död.