Военную службу начал в 1845 году, в чине унтер-офицера лейб-гвардии Преображенского полка. Участник Крымской войны 1853—1856 годов и непосредственно обороны г. Севастополя (1854—1855). Участвовал в подавлении Польского восстания (1863). В 1864 году перешёл с армейской на жандармскую службу, получив назначение на должность начальника штаба Отдельного корпуса жандармов, затем — товарищ шефа жандармов (1874), шеф жандармов и начальник Третьего отделения Собственной его императорского величества канцелярии (1876).
Погиб в результате теракта — 4 августа 1878 года на Михайловской площади (ныне — площадь Искусств) в Санкт-Петербурге С. М. Кравчинский нанёс ему смертельный удар кинжалом в брюшную полость.
Вот как описан последний день жизни генерала Мезенцова: «Николай Владимирович вставал обыкновенно очень рано и совершал ежедневно прогулки пешком, во время которых посещал часовню у Гостиного двора, на Невском. Зайдя туда и 4 августа, в девятом часу утра, Николай Владимирович по окончании молитвы в сопровождении своего бывшего товарища, отставного подполковника Макарова, направился обратно домой, через Михайловскую улицу, Михайловскую площадь и Большую Итальянскую улицу. Едва он вступил на мостовую Итальянской улицы и поравнялся с домом Кочкурова, перед самыми окнами кондитерской приблизились к нему двое шедших навстречу людей, весьма прилично одетых. Один из них нанёс ему рану кинжалом и вместе со своим спутником поспешно сел в поджидавший тут же экипаж. Г. Макаров сделал попытку задержать их, но в него сделали выстрел из револьвера, пуля пролетела мимо, а виновники катастрофы, никем не задержанные, так как в этой местности не было ни одного полицейского стража, а равно отсутствовала и публика, успели скрыться. Рассказывают, что они быстро поскакали по Итальянской и завернули на Малую Садовую; кучер, по всей вероятности, был из числа сообщников; рассказывают, что они будто бы и в предыдущие дни являлись на то же место, где были сегодня. Несомненно только, что преступники имели собственный экипаж, запряженный хорошею лошадью в серебряной упряжи. Заключают некоторые по этим признакам, что это люди со средствами. На одном из них было надето серое пальто. Сам Николай Владимирович в момент катастрофы не потерял присутствия духа, и когда выбежавшие на выстрел из кондитерской занятые в ней уборкой приказчики с ужасом спросили: „Кто ранен?“ — Николай Владимирович отвечал, что ранен он, и при этом указал на свою окровавленную одежду. При помощи полковника Макарова и вышедшего из соседнего дома камергера Бодиско, Николай Владимирович Мезенцов дошел по Итальянской до угла Малой Садовой, где его посадили на извозчика. Оттуда он доехал до своей квартиры у Цепного моста, на Фонтанке. Значительное истечение крови скоро обессилило раненого. Приглашенный в 11 часов утра доктор Мамонов, осмотрев больного, нашел, что положение его серьёзное. И действительно, несмотря на помощь, оказанную ему докторами во главе с знаменитым тогда хирургом Богдановским в 4 часа в области раны и желудочной полости открылись сильнейшие боли, и в 5 часов 15 минут в ужасных страданиях В. Н. Мезенцов скончался».
