За пръв път мястото до Дунав, където се намира градската градина, е описано през 1663 от Евлия Челеби. Равното място е осеяно с кестени и палми, твърди той. Днешният парк обаче се изгражда по-късно – през 1878 – 1899 година.
Моделът е заимстван от австрийските барокови паркове. Целта е била дърветата да привличат гражданите през всички сезони. Не случайно зелените лете листа, през есента стават червени, жълти, оранжеви. Иглолистните пък зиме са черни, а пролет – зелени.
През 1892 година общината назначава градинар, австрийски възпитаник, да се грижи за парка. През 1930 паркът е разширен до крепостта “Баба Вида”, като само за един ден видинчани са засадили 18 000 млади фиданки. През 1987 г. паркът е продължен в другата му част – от речната гара до колодрума. Сега паркът се простира по цялата част на града, граничеща с Дунав.
До днес са оцелели дървета от първото засаждане, които са над 100 години. Интересни са вековни летни дъбове, бяла топола с огромна височина. Липите са над 70 годишни. Новите дървета, които се засаждат, са кедри, смърчове, чинари. Липовата алея си остава любимо място за видинчани по-всяко време на годината.
В крайдунавския парк на Видин се намират и едни от знаковите сгради на града – драматичният театър, турската поща, джамията на Осман Пазвантооглу, крепостта “Баба Вида”. През последните години Видин се прости с няколко обичани парка – “Майски лес”, “Нора Пизанти”, където дърветата бяха изсечени, а нови не са засадени.