Трасса Миллионной улицы начала формироваться в первые годы существования Санкт-Петербурга, это одна из самых старых улиц в городе. Сразу после основания осенью 1704 года Адмиралтейства на том же левом берегу Невы начали селиться высшие морские чины во главе с самим царём Петром I. Задние дворы их участков образовали будущую нечётную сторону Миллионной улицы. В то же время на берегу Мойки появились Немецкая и Греческая слободы. Их граница проходила примерно по современному Мошкову переулку. Греческая слобода простиралась до Марсова поля, а Немецкая - до трассы современного Невского проспекта.
Греческая слобода получила своё название по дому грека шаутбенахта (контр-адмирала) И. Ф. Боциса. План 1714-1725 годов показывает наличие в Греческой слободе 51 дома. Здесь жили моряки - греки, португальцы, датчане. По распоряжению вице-адмирала К. И. Крюйса от 22 января 1710 года "в доме шаутбенахта Боциса должны были собираться все греки и итальянцы, служившие в русском флоте, для приятия указов". В том же 1710 году вблизи от начала нынешнего Аптекарского переулка в доме шотландца Александра Гордона была построена первая в Петербурге католическая церковь. К юго-западу от неё появилась лютеранская кирха. Рядом возник Финляндский рынок, на месте которого теперь находится Круглый рынок.
В Греческой (Немецкой) слободе жил генерал-адъютант, с 1718 года генерал-полицмейстер Петербурга Антон Девиер. Одним из его соседей был Роман Виллимович Брюс, старший брат известного Якова Брюса, с 1705 года бывший обер-комендантом Петербурга.
Немецкую слободу называли ещё и Финскими шхерами, там как здесь жило много финнов и пленных шведов. План 1714-1725 годов показывает в Немецкой слободе 70 домов. Здесь обитали царские врачи, военные, портняжные мастера. Рядом с ними жили приближённые царя генерал-майор Григорий Петрович Чернышёв, Савва Лукич Рагузинский-Владиславич.
У Миллионной улицы есть свой день рождения. 20 мая 1715 года Пётр I утвердил план урегулирования этой части города. Согласно плану от Красного канала до Зимнего дворца проложили улицу, которой следовало быть "7 сажени шириною и так погнутой, как сваями назначено". В её начале была выкопана гавань, куда зимой на хранение заводились принадлежащие местным жителям лодки.
В 1718-1719 годах будущую Миллионную улицу пересёк рукотворный канал - Зимняя канавка. Она была создана для того, чтобы от Зимнего дворца Петра I царь мог выплыть в Неву или Мойку. Тогда же через Зимнюю канавку был построен первый разводной мост.
До 1738 года петербургские улицы не имели официальных названий. Вместе с тем, в императорском указе от 16 ноября 1715 года будущая Миллионная улица названа Большой, в то время она выделялась своей длиной. На первых планах Петербурга улица обозначается как Почтовая, так как на месте Мраморного дворца тогда находился Почтовый двор.
За Почтовым двором вдоль Невы до Адмиралтейства стояли жилые дома. Их задние дворы обозначили северную сторону Миллионной улицы. К 1715 году здесь жили капитан флота И. К. Муханов, царский повар И. Фельтен, поручик Д. Чевкин, дьяк Фёдор Воронов, садовник князя Меншикова Василий Павлов, приближённый царя А. В. Кикин, писарь Преображенского полка А. Иванов, шлюзных дел мастер Антон Броус, доктор Арескин, штаб-лекарь Ян Говий, госпитальный аптекарь Торуп, князь В. В. Долгоруков, граф И. А. Мусин-Пушкин, корабельных дел мастера Г. А. Меншиков и Ф. М. Скляев, вице-адмирал Крюйс, "иноземец" Питер Николаев, генерал-майор Г. П. Чернышёв, генерал-аншеф П. И. Ягужинский, дипломат С. В. Рагузинский, генерал-адмирал Ф. М. Апраксин. Здесь же находился Зимний дворец Петра I [2, с. 9].
В 1717 году участок дома №21 стал принадлежать гофинтенданту Петру Ивановичу Мошкову. По его имени стал называться пересекающий Миллионную улицу переулок.
21 октября 1719 года в присутствии Петра I и Екатерины был официально открыт Красный канал, в него пустили воду. Этот канал проходил по западной стороне Марсова поля, у Невы заканчивался ранее созданным гаванцем. Через водную протоку был сооружён подъёмный мост. В 1722 году на участке дома №4 построили главную городскую аптеку.
В 1730-х годах одновременно существовали три названия магистрали - Немецкая (с 1733 года), Греческая (с 1734) и Милионная (с 1736). Причём до 1874 года слово "Милионная" на картах писалось через одну будку "л". Первые два названия связаны со слободами, через которые проходила улица. Миллионной же её стали называть по так называемому Миллионному дому графа П. Б. Шереметева (дом №19), поражавшего современников своей роскошью [2, с. 403]. Часто такое имя улицы связывают с тем, что здесь почти во всех домах жили самые богатые петербуржцы.
Огромную роль в судьбе Миллионной улицы сыграл пожар августа 1736 года. Тогда сгорели почти все дома в Греческой и Немецкая слободах. Это дало повод к началу нового урегулирования района, запрету на строительство здесь деревянных зданий.
20 апреля 1738 года указом императрицы Анны Иоанновны улица получила официальное название Большая Немецкая.
При правлении императрицы Елизаветы Петровны Миллионную улицу продлили через Царицын луг (Марсово поле) до Лебяжей канавки. В это время магистраль активно застраивалась каменными домами богатых людей. Они строились на высоких подвалах, дабы сохранить имущество во время наводнений. Это было закреплено законодательно, уровень первого этажа следовало поднимать не ниже чем на 71 сантиметр выше прибылой воды. Поэтому пороги домов находились на высоте от 1,75 до 2,6 метра над землёй.
С начала 1740-х годов в первых и полуподвальных этажах жилых зданий открывались магазины и увеселительные заведения. При Екатерине II на Миллионной улице устраивались скачки на рысаках, запряжённых в кареты, в которых сидели придворные дамы и их кавалеры.
Английский медик Томас Димсдель в конце июля 1768 года поселился по его словам на "одной из лучших улиц в городе" - Большой Миллионной. 12 октября в 10 часов утра он сделал прививку от оспы Екатерине II. К середине XIX века из 13 врачей, практиковавшихся в 1-й Адмиралтейской части, шесть принимали пациентов на Миллионной улице.
В 1760-1780-х годах велось строительство Мраморного дворца (дом №5) - подарка Екатерины II своему фавориту графу Орлову.
В 1783 году каменный мост в створе Миллионной улицы, который был перекинут через Красный канал, переместили на Зимнюю канавку. Это было связано с засыпкой Красного канала, переправа там была уже не нужна. Так появился каменный 1-й Зимний мост.
К концу XVIII века из-за близости Зимнего дворца здесь жили в основном представители аристократии. Если дом принадлежал людям незнатным, то он чаще сдавался в наём. В 1789 году магистраль снова стали называть "Милионной" - так было престижнее. До середины XIX века встречался также вариант "Большая Миллионная", тогда как "Малой Миллионной" назывался начальный участок Большой Морской улицы. В середине XIX века магистраль называли ещё и Троицкой, так как во дворце принца Ольденбургского с 1860 года находилась церковь Святой Троицы [2, с. 403]. В некоторых источниках говорится, что "Троицкая" - одно из первых названий магистрали, так как примерно от неё, то есть от Царицына луга, начинался перевоз через Неву к Троицкой площади.
С 1808 года в доме №25 размещалось французское посольство. В 1817-1821 годах было построено здание для размещения Павловского полка (дом №2). С конца XVIII века по 1830-е годы в доме №21 располагалась военная комендатура (в то время она называлась ордонансгаузом).
В 1834 году всем домам Петербурга была дана нумерация не по частям города, а по улицам. На Миллионной улице номера домов тогда начинались от Адмиралтейства. В обратную сторону их поменяли только в 1858 году.
В 1839-1852 годах было построено здание Нового Эрмитажа (дом №35). Оно завершило формирование панорамы Зимней канавки, которую лучше всего наблюдать как раз с Миллионной улицы.
В середине XIX века по Миллионной улице ездил общественный транспорт - омнибусы. Кареты разных маршрутов отличались цветом. Здесь проезжали тёмно-зелёные, на них от Аптекарского переулка можно было уехать в сторону Калинкина моста. Летом маршрут начинался не от Аптекарского переулка, а от Александровского парка на другом берегу Невы.
На рубеже XIX-XX веков во многих домах Миллионной улицы работали мелочные лавки, кондитерские, булочные, табачные и чайные магазины, лавки по продаже одежды, вин, различные мастерские.
В октябре 1918 к годовщине Октябрьской революции многие улицы Петрограда получили новые имена. Миллионная стала улицей Халтурина, по фамилии Степана Николаевича Халтурина, революционера-террориста, устроившего 5 февраля 1880 года взрыв в Зимнем дворце. При этом покушении на Александра II царь не пострадал, но было убито и ранено более 40 человек.
В 1930-х годах по улице Халтурина ходил автобусный маршрут №1, он сворачивал в Мошков переулок.
4 октября 1991 года магистрали вернули прежнее название - Миллионная улица.
