Kriza u bivšoj jugoslovenskoj Republici  Sjevernoj Makedoniji, koja je počela u februaru 2001. i završila Ohridskim Sporazumom u augustu 2001. rezultirao je sa 22 poznata slučaja nestanaka i vjerovatno sa još nekoliko desetina slučajeva.

Na poziv Predsjednika Republike, ICMP je otvorio ured u Skoplju novembru 2002. Iako je broj nestalih osoba bio relativno mali, ovo pitanje je prijetilo da omete provođenje Ohridskog Sporazuma od kad su članovi Vlade u to vrijeme krize i članovi bivše Državne oslobodilačke armije bili optuženi za umiješanost u nestanke ljudi.

ICMP je radio prema uspostavljanju jednog transparentnog, lokalnog procesa za nestale, uključujući uspostavu jedne ad hoc komisije koja je trebala biti direktno odgovorna vladi i pravosuđu.

Vlada je imenovala dva Koordinatora za pitanja nestalih u decembru 2003. da rade sa predstavnicima ICMP-a i relevantnih  državnih vlasti.  Tako je ICMP bio u mogućnosti pružiti pomoć Republici Sjevernoj Makedoniji pri identifikaciji devet nestalih osoba.

Parlament je 2011. izglasao primjenu Zakona o amnestiji iz 2002.godine. Prvobitno donesen u kontekstu Ohridskog Sporazuma, Zakon o amnestiji posmatra se kao napor da se podrži mirovni proces, ali na račun sudskih kazni. Kao takav, imao je niz ozbiljnih, negativnih uticaja na napore koji su se ulagali prema pronalasku osoba koje se i dalje vode kao nestali u vrijeme krize koja se desila 2001.