Родился 5 января 1871 года, образование получил в Воронежском реальном училище. 14 августа 1890 года зачислен юнкером на военно-училищный курс при Московском пехотном юнкерском училище, из которого выпущен 5 августа 1891 года подпоручиком в 14-й гренадерский Грузинский полк.
Произведённый 5 августа 1895 года в поручики Болховитинов поступил в Николаевскую академию Генерального штаба которую окончил в 1898 году по 1-му разряду. Сразу после выпуска, 17 мая, был произведён в штабс-капитаны и назначен в Приамурский военный округ. С 19 октября 1899 года состоял обер-офицером для поручений при штабе Приамурского военного округа и в этом качестве принял участие в Китайском походе 1900—1901 годов, 9 апреля 1900 года произведён в капитаны. За боевые отличия против китайцев был награждён орденами св. Станислава 3-й степени с мечами и бантом, св. Анны 3-й степени с мечами и бантом, св. Станислава 2-й степени с мечами и св. Владимира 4-й степени с мечами и бантом.
19 февраля 1902 года Болховитинов был назначен обер-офицером для поручений при штабе Квантунской области (в Порт-Артуре), с 5 сентября 1903 года числился старшим адъютантом штаба Квантунской области, однако к месту службы прибыл лишь 8 ноября, поскольку с 1 ноября 1902 года отбывал цензовое командование ротой в 16-м Восточно-Сибирском стрелковом полку, 6 декабря 1903 года произведён в подполковники.
С началом русско-японской войны Болховитинов был назначен старшим адъютантом временного штаба наместника на Дальнем Востоке, с 3 марта 1904 года являлся штаб-офицером для делопроизводства и поручений в управлении генерал-квартирмейстера полевого штаба наместника на Дальнем Востоке. С 5 по 24 августа 1905 года был штаб-офицером для особых поручений при начальнике штаба Главнокомандующего на Дальнем Востоке и с 25 августа 1905 года по 5 июля 1907 года занимал должность штаб-офицера для поручений при управлении генерал-квартирмейстера 1-й Манчжурской армии. За боевые отличия против японцев в 1904 году был награждён орденом св. Анны 2-й степени и 18 июня 1906 года получил золотое оружие с надписью «За храбрость» (по другим данным он это оружие получил в 1905 году). В том же 1906 году произведён в полковники (со старшинством от 10 июля 1905 года).
С 5 июля 1906 года Болховитинов являлся делопроизводителем в отделении генерал-квартирмейстера Главного управления Главного штаба, числясь на этой должности он с 9 мая по 1 сентября 1908 года отбывал цензовое командование батальоном в 8-м Финляндском стрелковом полку. 20 февраля 1911 года Болховитинов был назначен командиром 90-го пехотного Онежского полка. Параллельно он принимал активное участие в работе над «Военной энциклопедией», готовившейся к изданию в товариществе И. Д. Сытина.
Произведённый 21 июня 1914 года в генерал-майоры Болховитинов тогда же был назначен генерал-квартирмейстером штаба Кавказского военного округа, со 2 октября был генерал-квартирмейстером штаба Кавказской армии. 31 января 1915 года Болховитинов был назначен исполняющим дела начальника штаба Кавказской армии. Однако генерал Н. Н. Юденич не включил Болховитинова в состав полевого штаба Кавказской армии и он оставался при штабе наместника на Кавказе князя И. И. Воронцова-Дашкова. С 9 июня 1917 года Болховитинов был переведён на Западный фронт и числился в резерве чинов при штабе Петроградского военного округа, в начале августа получил в командование 1-й армейский корпус и 23 августа был произведён в генерал-лейтенанты с утвержденим в занимаемой должности.
В 1918 году поступил в РККА, где, числясь при Высшем военном совете, находился при штабе Главкома Красной армии Северного Кавказа. В августе 1918 года при занятии Екатеринодара частями Добровольческой армии, пробрался в город, где проживала его семья и был белыми арестован. Предан военно-полевому суду Добровольческой армии, который приговорил его к смертной казни. Генерал Деникин заменил приговор суда разжалованием в рядовые, в качестве которого Болховитинов около года служил в частях Дроздовской дивизии. За отличия в боях был восстановлен в чине генерал-лейтенанта. В начале 1920 года принял от генерала Букретова должность военного министра Кубанского правительства. Во время отступления Кубанской армии от Новороссийска на юг Болховитинов был эвакуирован на судах в Крым. В войсках генерала Врангеля он занимал должность инспектора классов Кубанского Алексеевского военного училища, с которым в ноябре 1920 года отплыл на остров Лемнос, затем прибыл в Тырново-Сеймен в Болгарии, где оставался инспектором классов Кубанского училища до 1924 года.
10 июня 1925 года Болховитинов покончил жизнь самоубийством в поселоке Харманли, похоронен на местном кладбище. Генерал Деникин считал, что причиной самоубийства Болховитинова стали статьи бывшего начальника Северо-Кавказского военно-революционного штаба Владимира Чёрного, возглавлявшего подпольный центр Чрезвычайной комиссии на Кубани, в которых он утверждал, что Болховитинов, находясь в рядах Добровольческой армии, оставался агентом ЧК и исполнял «все наши поручения… точно и безоговорочно». Частью эмигрантского общества эта версия воспринималась как достоверно установленный факт. Позже авторы написанной с сепаратистских позиций книги «Вольное казачество» (Париж, 1936) приняли на веру показания В. Черного о предательской деятельности генерала Болховитинова и писали о ней так, как если бы это был твердо установленный факт (с. 168), при этом они подчеркивали, что генерал Болховитинов был «не казак», а «русский». «Придет время — откроется многое», — закончил свою статью генерал А. И. Деникин.