Bombardovanje Savezne Republike Jugoslavije zatekla ga je na dužnosti komandanta 204. lovačkog puka, čije je sedište bilo izmešteno u Staru Pazovu.
Oko 12 časova 4. maja 1999. primećena je veća grupa NATO aviona koja je dejstvovala u pravcu Valjeva, uglavnom na fabriku municije „Krušik“, kao i na vojna skladišta u selu Pričević. Komandu da poleti dobio je jedan od mlađih oficira, ali je potpukovnik Pavlović telefonskom vezom naredio da se pozvani pilot zadrži, a umesto njega poleteo je on u svom avionu MiG-29. Ubrzo se našao nad Valjevom, ali se posle samog uzletanja na njegovom avionu pokvario generator naizmenične struje tako da je ostao bez radara. Pavlović se upustio se u neravnopravnu bitku i ubrzo je, oko 12 i 35, bio pogođen sa tri rakete. Poginuo je još u vazduhu. Poslednje reči su mu bile: „Imaju me!“, a ostaci njegovog aviona pali su u blizini sela Petnica.

Sahranjen je 6. maja 1999. na Bežanijskom groblju. Iza sebe je ostavio suprugu Slavicu, i sinove Srđana i Nemanju.
Nikada nije proglašen za heroja. Odlikovan je posthumno Ordenom za hrabrost i Zlatnom letačkom značkom.
Drugog maja 2005. godine u Gornjem Crniljevu otkriven je spomen kompleks koji obuhvata spomen-česmu na kojoj je krilo sa oborenog aviona MiG-29, i spomen-dom „Milenko Pavlović Pilot“, a u okviru kompleksa nalaze se i crkva Obnovljenja hrama sv. Georgija i igralište FK „Milenko Pavlović Pilot“.
RTS je snimio dokumentarni film pod nazivom „Let u smrt“, koji govori o životu i radu Milenka Pavlovića, kao i o njegovim poslednjim trenucima. U filmu govore njegovi roditelji, supruga, sinovi, kolege i prijatelji.
Film možete skinuti na sledećem linku:
http://rapidshare.com/files/22672542/Pavlovic_final200.avi