Palić je nestao u julu 1995. godine kada je išao na pregovore sa Ratkom Mladićem kako bi ženama, starcima, djeci, bolesnim i ranjenim obezbijedio siguran izlazak iz enklave Žepa koja je trebala biti zaštićena zona UN-a. Palića su Mladićevi vojnici uhapsili u prisustvu vojnika UN-a, nakon čega mu se izgubio svaki trag.
Palićevi posmrtni ostaci ekshumirani su iz masovne grobnice u Vragolovima kod Rogatice u novembru 2001. godine, ali nisu bili identifickovani sve do augusta 2009. godine. Lokacija na kojoj je mučki ubijen Avdo Palić nije poznata. Prema nalazima obdukcije zaključeno je kako je najvjerovatnije ubijen pucnjem u glavu. Pretpostavlja se da mu je pucano s leđa.
U haškoj presudi general Vojske RS Zdravku Tolimiru, koji je osuđen na doživotnu kaznu zatvora, kao zločin genocida okvalikovano je i ubistvo pukovnika Avde Palića. Palić je sahranjen u augustu 2009. godine haremu Ali-pašine džamije u Sarajevu uz najviše vojne počasti
