Идея установить памятник Новороссийскому генерал-губернатору принадлежала Михаилу Толстому. Одесситы идею одобрили, а император Александр ІІ одним из первых пожертвовал на строительство памятника три тысячи рублей из собственных средств. Деньги на памятник вносили как члены царской фамилии, так иностранцы и обычные горожане.
Создание памятника поручили известному мюнхенскому скульптору Фридриху Бруггеру, работы которого находятся в Зале Славы и украшают Триумфальные ворота в Мюнхене. Для создания статуи скульптор воспользовался последним портретом Воронцова, кисти немецкого живописца Франца Крюгера, и сходство получилось практически полным. Архитектором памятника стал Франц Боффо.
Фигуру Воронцова отлили из бронзы, а постамент вырезали из редкой породы гранита — крымского диорита, добытого вблизи горы Аю-Даг, на территории имения Потемкина. Чтобы отколоть камни от гранитного массива, пришлось закладывать пороховой заряд. Таким образом были добыты 11 камней, самый маленький из которых весил более трех тонн. Для доставки глыб к кораблю, их пришлось перетаскивать практически вручную, так как из-за скал и оврагов использовать тягловую силу было невозможно. Более трех месяцев этой работой занимались около 70 человек.
Погрузить камни в корабельный трюм не удалось из-за их веса и размеров, а сильный ветер, который начался во время путешествия, едва не перевернул судно. Но все окончилось благополучно, если не считать, что по прибытии в Одессу камни вновь пришлось доставлять к месту установки памятника при помощи рабочих.
На открытие и освящение монумента собралась вся Одесса. Высота готового памятника составляла более восьми метров, из которых 3,2 метра приходится на бронзовую фигуру князя. Ограда состояла из 12 чугунных тумб, украшенных гербом Одессы и цепями. На барельефах памятника изобразили сцены сражений, в которых отличился Воронцов.
В 2009 году памятник Михаилу Воронцову принят под охрану государства как памятник монументального искусства национального значения.