Название Виленский переулок было присвоено 7 марта 1858 года по городу Вильно, как в середине XIX века именовался нынешний Вильнюс – столица Литвы. 29 сентября 1922 года переулку повысили статус и назвали улицей Красной Связи. В это время в конце переулка, в доме № 8 по Парадной улице, находились казармы подразделений военных связистов. Поскольку в молодой советской республике буквально все должно было быть красным, в революционном смысле этого определения, то и улица получила соответствующее название.

Это название оказалось неудобным в употреблении, оно не стало исторически ценным и обоснованным, поэтому 13 января 1998 года оно было отменено. Вместо улицы Красной Связи вновь появился Виленский переулок.

Эта небольшая улица находится на Гутуевском острове. Она проходит от Межевого канала до Двинской улицы. Название присвоено 16 апреля 1887 года по латвийскому городу Виндаве вслед за соседними проездами (Двинской, Гапсальской улицами, Рижским проспектом), получившими в 1859 году имена по прибалтийским городам. Виндава – это польский вариант латышского топонима Вентспилс – «город на реке Венте».

В 1896 году (официально – 22 мая 1900-го) улица была продлена на юг до не существующего ныне Сельдяного канала, но в 1969 году в связи со строительством новых домов по Двинской улице этот участок был упразднен.

До 1988 года проезд, который отходит от Загородного проспекта и идет параллельно Подъездному переулку и Витебской железнодорожной линии, оставался безымянным.

С наименованиями ему вообще со времени своего возникновения не везло. На карте 1798 года он обозначен как 6-я улица, в соответствии с применявшейся тогда нумерацией проездов в слободе Семеновского полка. Вскоре этот номер был утрачен, и улица превратилась в безымянный проезд. 16 апреля 1887 года ему присвоили название Егерский переулок, по лейб-гвардии Егерскому полку, казармы которого, построенные в 1815 году по проекту Александра Штауберта, находились неподалеку, на Рузовской улице, 16–18. Однако из-за того, что казармы находились не в самом переулке, а с противоположной стороны железной дороги за Введенским каналом, да и полк после Октября 1917-го был расформирован, название просуществовало сравнительно недолго и к 1929 году было окончательно утрачено.

Наконец, 4 апреля 1988 года была предпринята третья попытка дать проезду имя. Он стал Винокурцевским.

Новое название дано в честь участкового уполномоченного 13-го отделения милиции Ленинского района Ленинграда Павла Дмитриевича Винокурцева (1905–1941). 8 ноября 1941 года, находясь в зоне обстрела, Павел Винокурцев обеспечивал общественный порядок, помогал гражданам укрываться в бомбоубежищах. Когда на улице разорвалось несколько снарядов, он заметил около стены дома девочку, которая в ужасе металась возле убитой матери. Схватив ребенка на руки, Винокурцев побежал к ближайшему укрытию, но в это время разорвался очередной фашистский снаряд. Спасая ребенка, участковый успел прикрыть девочку своим телом, но сам погиб. К сожалению, не удалось узнать ни имени девочки, ни ее дальнейшую судьбу.

Однако в истории Ленинграда-Петербурга сохранилось имя Павла Дмитриевича Винокурцева. И хотя по проезду не числится ни одного дома и название практически не употребляется, о подвиге милиционера напоминает мемориальная доска. Она установлена на стене наземного вестибюля станции метро «Пушкинская», со стороны Винокурцевского проезда.

Площадь перед Витебским вокзалом появилась одновременно со строительством в 1837 году первого здания вокзала, но до 1930-х годов главной архитектурной доминантой здесь был вовсе не вокзал, а стоявший на противоположной стороне Загородного проспекта Введенский собор лейб-гвардии Семеновского полка, возведенный в 1837–1842 годах по проекту Константина Тона. Соответственно, и площадь с 1843 года именовалась Введенской. Мимо площади протекал Введенский канал, называвшийся так еще с 1803 года по предыдущей Введенской церкви, находившейся на том же месте. Канал был засыпан в 1967 году, но его имя сохраняет проходящая на его месте улица.