Крестовский остров – последний из знаменитой триады Кировских островов. На старинных картах допетербургского периода он называется Ristisaari, что с финского языка переводится как «Крест-остров». Как утверждают исследователи, это название связано с придорожными надмогильными крестами, которые в давние времена служили ориентирами для путешественников. К идее креста сводятся и многочисленные легенды о происхождении названия острова. «Одни связывали это название с крестообразной формой озера, якобы находившегося здесь, другие указывали на находку на острове какого-то большого креста, третьи полагали, что поводом для наименования острова послужила часовня с крестом, упоминаемая в писцовой книге XVI века». Сохранилось предание и о некой первой каменной постройке на острове, будто бы имевшей форму Андреевского креста. Кроме того, в те далёкие времена на острове, или, как выражается современная молодежь, «На крестах», в непроходимом лесу были якобы проложены в виде огромного креста две просеки: одна – вдоль острова, другая – поперёк. Это, как уверяют, и дало название острову.
В 1717 году Пётр I подарил остров своей любимой сестре Наталье, и на картах Петербурга появляется новое название: остров Святой Натальи. Понятно, что название относилось не к имени самой Натальи Алексеевны, а к имени её небесной покровительницы и защитницы, в день поминовения которой она родилась и в честь которой была названа при крещении.
В 1730-х годах владельцем острова стал фельдмаршал граф Бурхард Христофор Миних. В отличие от Натальи Алексеевны, он был менее разборчив в вопросах этики, морали или обыкновенного такта и, не мудрствуя лукаво, назвал остров своим именем. С 1741 года остров стал Христофоровским. Только в конце XVIII, а по некоторым источникам, даже в начале XIX века острову возвращают его первородное название. Понятно, что в русской транскрипции. Теперь он снова называется Крестовским.
В первой половине XX века западная часть острова застраивается особняками знати, а его восточная часть отводится для народных гуляний. Одними из первых освоили Крестовский остров петербургские немцы. В городском фольклоре сохранилась память о немецкой традиции празднования Ивановой ночи, или ночи на Ивана Купалу. Центром праздника стал Крестовский остров. В те времена посреди острова возвышался песчаный холм, на верхней площадке которого, по свидетельству современников, одновременно могли поместиться до ста человек. Фольклорное название этого холма «Кулерберг» произошло, по мнению многих исследователей, от немецкого глагола «kullern», что приблизительно означает «скатываться, ложась на бок». Будто бы так в очень далеком прошлом развлекались прапрадеды петербургских немцев у себя на родине в ночь на Ивана Купала. Со временем этот старинный ритуал приобрёл более респектабельные формы, и в петербургский период местные немцы уже не скатывались с «Кулерберга», а как можно более чинно сбегали с вершины холма, непременно парами, держась за руки – кавалер с дамой. От того времени в собрании петербургского городского фольклора остался микротопоним «Кулерберг».
В 1930-х годах на острове создается спортивный комплекс со стадионом имени С. М. Кирова в центре. В 1945 году на Крестовском острове в честь победы советского народа в Великой Отечественной войне заложили Приморский парк Победы. Планировка парка выполнена по проекту архитектора А. С. Никольского. Парк включен в единую систему северных парков, раскинувшихся на четырёх островах – Крестовском, Петровском, Каменном и Елагином. В композицию парка входят два искусственных пруда – Северный и Южный. Северный получил в народе название «Лебединое озеро».
В 1949 году, в рамках подготовки к празднованию 70-летия со дня рождения Сталина, в Ленинграде запланировали установку пяти монументов «любимому вождю всего человечества». Четыре из них – на Поклонной горе, на проспекте Обуховской обороны, на площади Победы и на площади перед Балтийским вокзалом – успели установить в ноябре того же года, буквально накануне всенародного юбилея. Пятым собирались украсить главную аллею Приморского парка. Он должен был стать самым величественным и представительным, олицетворяющим казавшуюся тогда главной и бесспорной «выдающуюся» роль Сталина в победе Советского Союза над фашистской Германией. Однако проектирование и изготовление монумента затянулось на несколько лет, а потом, после смерти Сталина и последовавшего разоблачения культа его личности, надобность в памятнике отпала. Сейчас на его месте сооружен фонтан.