Из семьи костромских дворян. Закончил юридический факультет Московского университета.
С 1861 был мировым посредником в Костромской губернии. В 1864 поступил на службу в Государственную канцелярию. С 1868 служил в Канцелярии Комитета министров. В 1880—1883 — товарищ министра государственных имуществ. Действительный тайный советник (1892), статс-секретарь. В 1883—1902 занимал пост управляющего делами Комитета министров; одновременно с 1893 был управляющим делами Комитета Сибирской железной дороги.
В 1897 председательствовал в комиссии из представителей различных ведомств по исследованию и решению земельного вопроса в Забайкалье (Комиссия Куломзина). Оказал значительное влияние на хозяйственное и культурное освоение Сибири. После его поездок в Сибирь (1896, 1897) стали интенсивно заселяться таёжные районы Тарского округа. В честь него одна из железнодорожных станций близ Омска носила имя Куломзина (ныне станция Карбышево).
Продвинул вперёд дело разработки залежей фосфоритов в России, установив в своём имении, Костромской губернии, Кинешемского уезда, их разработку на научной основе.
23 декабря 1902 назначен членом Государственного совета. С 1914 года председатель Романовского комитета для призрения сирот сельского состояния. С 15 июля 1915 по 1 января 1917 года — председатель Государственного совета. В августе 1915 избран председателем Наблюдательной комиссии Особого совещания для обсуждения и объединения мероприятий по обороне государства. Занимался научной деятельностью, автор ряда научных трудов, в том числе по истории финансов в России. После революции эмигрировал во Францию.
Член Русского географического общества, председатель первого съезда представителей губернских ученых архивных комиссий, помощник председателя Русского исторического общества, автор воспоминаний «Пережитое», в которых даны яркие картины положения переселенцев в Сибири.
После окончания учёбы занялся исследованияи финансовых учреждений Англии и Франции, написал несколько статей по этой теме. Научную карьеру пришлось прервать после того как он занял должность мирового посредника в родном Кишиневском уезде. Однако от научной деятельности не отходил и в дальнейшем. С 1871 года состоял в Русском историческом обществе, а в 1906 году стал помощником его председателя. Был почётным членом Русского географического общества, Археологического института в Петербурге, а так же минералогического и Астрономического обществ. Внёс вклад в развитие Императорской и Харбинской публичных библиотек.
Занимался проблемами переселения и крестьянским вопросом. В частности руководил составлением статистических сводов по сельскому населению Европейской России в канцелярии Комитета министров в результате длительной работы был создан «Свод статистических материалов, касающихся экономического положения сельского населения Европейской России» (СПб 1894 г.). Основная цель этой работы была, доказать наличие избыточного крестьянского населения. Так же под его руководством было издано 16 выпусков статистических материалов о землепользовании в Забайкальской области.
В 1910 году в соавторстве с В. Г. Рейтером-Нолькеном, написал и издал биографию известного государственного деятеля М. Х. Рейтерна.
В 1911 году издал брошюру «Пора бы это оставить» в которой поднимал проблему пьянства и борьбы с ней.
Под его редакцией было опубликовано и множество документов по истории финансов в годы правления Екатерины II, Павла I и Александра I. Так же Анатолий Николаевич активно публиковался в журналах «Вестник Европы», «Русское слово», «Юридический вестник», «Экономист», «Сельский вестник».
Кроме всего этого Анатолий Николаевич Куломзин активно занимался вопросами образования и просвещения. Активно поднимал проблему необходимости развития образования, в частности в на в Сибири. Однако не найдя поддержки ни в Министерстве народного просвещения ни в Синоде организовал через Комитет Сибирской железной дороги обширную общественную деятельность по школьному строительству в Сибири. Был автором одного из проектов введения всеобщего обучения.
Зять министра юстиции Д. Н. Замятнина. Дети: Анатолий Анатольевич — камергер двора, Яков Анатольевич — камер-юнкер, Екатерина Анатольевна — супруга Н. И. Шидловского, депутата III и IV Государственной думы.
Написал следующие произведения: