Утром 5 марта 2000 года, во время неравного боя с чеченскими боевиками, потратив все силы и патроны, раненый Андрей выдернул чеку последней гранаты и подорвал себя и боевиков. За мужественный подвиг 26 апреля 2000 года бойцу курского ОМОН сержанту милиции Андрею Хмелевскому было присвоено звание «Герой России» (посмертно).
Именем Андрея Хмелевского названа средняя общеобразовательная школа № 20 в г. Курске. Мемориальные доски установлены на здании городского дворца пионеров и школьников, на фасаде здания Курского техникума связи и школы № 20.
В 2016 года его именем названа улица в микрорайоне «Соловьиный» г. Курска.