Название моста переводится с английского как Мост Тысячелетия, поскольку постройка этого сооружения была в ознаменование наступления третьего тысячелетия; мост стал одним из немногих масштабных сооружений, которые были построены в столице Англии в связи с празднованием Милленниума.
Строительство началось в конце 1998 года. Основные работы начались 28 апреля 1999 года. На строительство моста было потрачено £18,2 миллиона (при бюджете £2,2 миллиона).
Перед постройкой предварительно на обоих берегах реки Темзы, именно в тех местах, которые предназначались для строительства, были проведены археологические раскопки.
У моста не одна, а две даты открытия. Первый раз, 10 июня 2000 года, мост торжественно открыли в присутствии королевы Англии Елизаветы II. В тот день на мосту побывало около 100 000 человек. Вместе с этим на мосту находилось до 2 000 человек. Однако вскоре обнаружилась неприятная новость — мост очень сильно качался из стороны в сторону; происходило это из-за своеобразных резонансных явлений; естественно, что инженеры, проектирующие мост, даже и не задумывались об этом. После обнаружения дефекта моста сначала предприняли попытку уменьшить численность людей, которые проходили по мосту одновременно; однако такой принцип действий привёл к скоплению длинных очередей. В итоге 12 июня 2000 года мост был закрыт для его реконструкции. В народе получил прозвище «шаткий» (англ. The Wobbly Bridge).
После закрытия началась перестройка моста Тысячелетия — инженеры приняли решение добавить в его конструкцию демпферы. После этого была проведена проверка: по мосту прошли 2 000 добровольцев и они доказали, что проблема раскачивания моста устранена. Мост Тысячелетия открыли снова. Это произошло 22 февраля 2002 года. С того времени подобные явления не наблюдались. 18 января 2007 года мост Тысячелетия временно закрыли по причине сильного ветра: в эти дни в большей части Европы свирепствовал ураган под названием «Кирилл»; мост был закрыт по той причине, что ураган мог просто сдуть людей с моста.
Мост Милленниум - самый молодой мост центрального Лондона (если не считать пешеходных мостов Хангерфорд - но те были построены в качестве замены существовавших ранее пешеходных галерей вокруг одноимённого железнодорожного моста). Это первый новый мост (а не перестроенный старый), возведённый в центральном Лондоне за последнее столетие (предыдущим был Тауэрский мост).
