Генерал Н.И. Евдокимов скончался 22 мая 1873 г. и с воинскими почестями был погребен у пятигорского Спасского собора. На средства, собранные жителями Пятигорска и Железноводска, над могилой графа была воздвигнута величественная мемориальная часовня из серого кавказского гранита с образом Спасителя внутри и неугасимой лампадой. В 1878 г. в часовне были установлены мраморный пьедестал и бюст Н.И. Евдокимова работы известного Петербургского скульптора Н.А. Лаверецкого.
По своей архитектуре часовня была достаточно оригинальной и отличалась от традиционных церковных конструкций. Ее квадратное основание было украшено стилизованными башнями с зубцами, делавшими всю часовню похожей на крепость. Крепостные зубцы шли по верхнему краю стен и вершине приделов, а четыре башенки, укрепленные по углам крыши имели даже стилизованные бойницы. По обеим сторонам входа на стене были укреплены стволы артиллерийских орудий, а над входом – на фронтоне, выполненном так же в стиле укрепления крепостных ворот, размещался герб графа Евдокимова. Крышу часовни простой треугольной, а не церковной луковичной формы, венчал шар, на котором возвышался ажурный крест.
В годы постреволюционного богоборчества она, как и Спасский собор, была разрушена. После уничтожения собора и часовни бюст генерала перенесли в Пятигорский краеведческий музей. 14 июня 2013 года на месте захоронения генерала Н.И. Евдокимова была установлена мемориальная доска.