Еще у острова были такие названия: Круглый, Приморский, Новосильцов. В середине XVIII века остров принадлежал богатому поручику Новосильцеву, который скоро продал его олонецкому купцу и судостроителю К. Гутуеву. Этот предприниматель стал советником департамента гражданских дел городского магистрата. По его фамилии Гутуевским начали называть и остров, и появившийся позже мост через Екатерингофку.
В 1878–1885 годах был сооружен Морской канал. Тогда на Гутуевский остров и на острова, которые располагались рядом, из Кронштадта перенесли торговый порт.
Ранее это был остров Голодай. Такое название использовалось около 200 лет. У историков есть несколько версий относительно происхождения этого названия. Некоторые придерживаются мнения, что оно произошло от шведского слова халауа (в переводе на русский означает «ива») или от английских слов холи дэй («святой день, праздник»). В записках старых историков Петербурга есть сведения, что название Голодай возникло из-за неправильного произношения английской фамилии Т. Голлидэя. Это был врач, который владел участком земли на острове.
В других архивных записках было указано, что название появилось из-за того, что в начале XVIII века в землянках и бараках на острове жили крестьяне-строители. Их жизнь была очень тяжелой, они голодали. И появилось такое печальное для нашего слуха название. Однако большинство историков все-таки склоняются к версии, что причиной названия острова была фамилия Голлидэй. А русские люди уже переосмыслили незнакомое слово, придали ему понятный смысл.
В советское время Голодай получил название остров Декабристов. Выдвинули предположение, что именно здесь были погребены тела казненных в июле 1826 года руководителей восстания декабристов – К. Рылеева, П. Каховского, П. Пестеля, М. Бестужева-Рюмина, С. Муравьева-Апостола. На острове, в западной его части, есть памятник декабристам, который был заложен в 1926 году. В конце XIX – начале ХХ века с Голодаем слились острова Кошеварова, Горнапуло, Жадимирского. А уже к острову Декабристов был присоединен бывший Вольный остров.
Расположенный в юго-западной части дельты Невы, этот остров в первой половине XVIII века назывался Батарейным, так как принадлежал ведомству Адмиралтейской коллегии. На берегу, обращенном к заливу, стояла артиллерийская батарея. В конце XVIII века у острова появилось другое название – Канонирский (потом Канонерский): слово канонир (канонер) французское, в переводе на русский означает «пушкарь»; так называли морских артиллеристов. Долгое время остров использовали в качестве полигона для обучения морских артиллеристов стрельбе. В 1880-х годах, когда закончилось строительство Морского канала, порт перенесли на Гутуевский остров. А на Канонерском острове построили судоремонтные мастерские.
Остров находится в северной части дельты Невы. У него было много владельцев. Отсюда и множество названий, которые существовали в разное время. На плане Петербурга 1717 года он значится как остров Святой Натальи – дело в том, что Петр I подарил остров своей сестре Наталье. В 30-х годах XVIII столетия остров пожаловали графу Христофору Миниху. Он назвал остров Христофоровым в свою честь. Но название просуществовало не слишком долго. Следующими владельцами острова были графы Разумовские и князья Белосельские-Белозерские.