Մակեդոնիայի Հանրապետության կառավարության խնդրանքի հիման վրա՝ կանխելու Սկոպիեի (Մակեդոնիայի մայրաքաղաք) կառավարության և էթնիկ ալբանացի ապստամբների միջև հակամարտության սրումը, ՆԱՏՕ-ն մասնակցել է տարածաշրջանում ընթացող գործընթացներին։ 2001 թվականի հունիսին Մակեդոնիայի Հանրապետության նախագահ Բորիս Տրոյկովսկին դիմեց ՆԱՏՕ-ին՝ խնդրելով օգնություն ցուցաբերել երկրի տարածքում Ազգային ազատագրական բանակի և էթնիկ ալբանացի ապստամբ խմբերին զինաթափելու գործընթացում։ ՆԱՏՕ-ի ջանքերի արդյունքում հակամարտող կողմերի միջև տեղի ունեցավ քաղաքական երկխոսություն, որին հաջորդեց խաղաղության շրջանակային ծրագրի մշակումը և ռազմական գործողությունների դադարեցումը տարածաշրջանում։ Օհրիդյան շրջանակային համաձայնագրի (Ohrid Framework Agreement) հիման վրա 2001 թվականի օգոստոսի 27-ին «Հարուստ բերքահավաք» ծածկագրային անվանումով գործողության շրջանակներում ՆԱՏՕ-ն ռազմական անձնակազմ ուղարկեց Մակեդոնիա։ ՆԱՏՕ-ի առաքելությանը հանձնարարվել էր Ազգային ազատագրական բանակի զինվորների կողմից ինքնակամ հանձնված զենքերը հավաքել և ոչնչացնել։ Երեսնօրյա գործողության արդյունքում ՆԱՏՕ-ի զինվորականները առգրավել են մեծ քանակությամբ զենք և տարբեր պայթուցիկ նյութեր, որոնք օգնել են կանխել քաղաքացիական հակամարտության սրումը։ Ավելի ուշ Սկոպիեի կառավարությունը խնդրանքով է դիմել ՆԱՏՕ-ին Մակեդոնիայի Հանրապետությունում ապակայունացումը կանխելու, Եվրամիության և ԵԱՀԿ դիտորդների անվտանգությունն ապահովելու նպատակով պահպանել փոքրաթիվ ռազմական քանակակազմ։ 2003 թվականի մարտից Մակեդոնիայում ՆԱՏՕ-ի առաքելությունը փոխանցվել է Եվրամիությանը (EU)։