През 1949 г. град Варна е преименуван на Сталин по повод 70-годишнината на диктатора. Взето е решение и за изграждането на негов паметник до колонадата на входа на Морската градина. Проектът е възложен на скулптора Христо Боев.
Близо месец в ателието си на бул. „Червеноармейски“ Боев доизпипва 60-сантиметровата глава на Сталин от глина. След одобрението на главата от специално назначена комисия от София през 1950 г. започва изграждането на целия паметник. По някакви причини, вероятно финансови, Изпълкомът на град Сталин нарежда „паметникът да се направи в цял ръст, от гипс, с временен характер“.
Откриването е изключително тържествено – с военноморската духова музика и с оръдейни залпове, в присъствието на бъдещия министър-председател Вълко Червенков, тогава член на ЦК на БКП, на военни от всички рангове от София и страната, на цялото партийно и административно ръководство на града. Създателите на паметника не са допуснати сред официалните гости.
След около 2 години и няколко ремонта на гипсовия паметник се взема решение да бъде изграден съвсем нов, а проектът отново е възложен на скулптора Христо Боев. Този път постаментът е от бяла чукана мозайка, самият паметник, отново от гипс, в него е поставена метална конструкция с височината на скулптурата. Новият паметник на Сталин е изграден от Христо Боев и Васил Ставрев. Няма съхранена информация за негово тържествено откриване.
Междувременно на 5 март 1953 г. Сталин умира. През февруари 1956 г., на 20-ия конгрес на КПСС, са докладвани противоречиви за биографията на Сталин факти, с много произтичащи от това последици. Една от тях е Априлският пленум на БКП, след който на 20 октомври Президиумът на Народното събрание издава указ за преименуване на град Сталин на Варна, отбелязва Николай Савов в книгата си „Паметниците на Варна“.
Скулптурата на Сталин е демонтирана през нощта срещу 13 март 1962 г. с голяма бързина и при изключителни мерки за сигурност от страна на милицията. След добре обмислен план за действие по мероприятието за разрушаването в 23 часа на 12 март МВР отцепва район в голям периметър. Към паметника подхождат работници, бордова „Татра“ – камион, и кран. В 23:30 часа завързват раменете със стоманени въжета, които преминават по лактите на Сталин, като ги стягат. Кранът повдига паметника, тогава подхожда камионът и го натоварват в легнало положение. Останала е само арматура, която се изкъртва и също се товари на камиона. Откарват го в двора на „Паркове и градини“, стоварват го и натрупват клони и шума, за да го прикрият. Действа се експедитивно и на мястото на разрушения паметник слагат райграс и засаждат цветя. Сутринта на 13 март е нямало и следа от нощната акция. Много любопитни варненци през деня идват да видят новия облик на Морската градина. Някои се радват, други недоволстват, но паметника от гипс, камъчета и арматура на Сталин го няма.
Все още няма коментари