Первоначально дорога начиналась от Пискаревского проспекта примерно там, где к нему подходит сейчас улица Маршала Тухачевского, и уходила на восток за Соединительную железнодорожную линию. Параллельно дороге южнее ее проходил не существующий ныне Анисимов переулок, по которому она и получила свое название. Впервые оно появляется в документах в 1955 году. Имя же переулка известно с 1901 года и происходило, по-видимому, от фамилии землевладельца.
В 1960-е годы в результате жилой и промышленной застройки почти все проезды, перпендикулярные Пискаревскому проспекту, исчезли, а адреса по ним еще некоторое время оставались, в том числе и дом № 41 по Анисимовской дороге. В результате Анисимовской дорогой по ошибке стали именовать другой проезд, проходивший перпендикулярно прежнему направлению от Уманского переулка на север вдоль железной дороги мимо вышеупомянутого дома № 41 и после четырех поворотов переходивший в Зотовский проспект. Границы между этими тремя проездами были и остаются настолько неясными, что в 1998 году при упорядочении нумерации домов по Уманскому переулку к нему отнесли и южную часть дороги до пересекающей ее железнодорожной ветки.
Переулок идет от Исаакиевской площади до Казанской улицы. Первоначально с 1781 года он именовался Новым. За все годы существования Петербурга в нем возникало много Новых улиц и переулков, но в центре города только этот переулок оставался Новым больше полутора столетий. Лишь 23 июля 1939 года он был переименован в честь Никиты Григорьевича Антоненко (1881–1906) – члена судового комитета восставшего в 1905 году крейсера «Очаков». Так в том году в Ленинграде отметили День Военно-Морского Флота – вместе с Новым переулком еще более десятка улиц были названы именами революционных матросов.
За участие в восстании Н. Г. Антоненко был расстрелян. Вместе с ним были расстреляны еще три руководителя восстания – П. П. Шмидт, А. И. Гладков и С. П. Частник. Набережная Лейтенанта Шмидта в городе есть, есть и улица Гладкова, наименованная в том же 1939 году, а вот четвертый организатор восстания не удостоился такой чести – видимо, власти сочли его фамилию идеологически невыдержанной.
Проезд между Дальневосточным проспектом и проспектом Большевиков 26 января 1970 года был назван улицей Антонова-Овсеенко, в честь одного из руководителей взятия Зимнего в октябре 1917 года, члена комитета по военным и морским делам первого советского правительства Владимира Александровича Антонова-Овсеенко (1883–1939).