Iako još uvijek nesigurne, veze između njih unaprijedile su se nakon pada režima Slobodana Miloševića 2000. godine, a tri godine kasnije, Srbija je podnijela zahtjev za članstvo u PfP.
Iako još uvek nelagodni, odnosi između Srbije i NATO-a poboljšali su se posle pada režima Slobodana Miloševića 2000. godine i, tri godine kasnije, Srbija je podnela zahtev za članstvo u PzM.