До створення парку Високий замок був улюбленим місцем прогулянок львів'ян. На північ, на схилах замку, знаходився санаторій "Кисельки", де у 1910 році померла Марія Конопніцька. Територія сьогоднішнього парку тоді називалася Стрийським передмістям, а землі належали місту ще за грамотою Казимира Великого в середині 14 століття.

Територія була вкрита болотами і хащами, не придатна ні для пасовищ, ні для забудови. Вона була важкодоступною, похмурою і небезпечною, оскільки слугувала притулком для втікачів, які переховувалися від правосуддя. У другій половині 19 століття, після створення Галицької автономії, влада намагалася подбати про статус міста, надаючи пріоритет усім інвестиціям, які б слугували вирізненню міста як столиці Галичини. Розвиток зелених зон і створення сучасного великого парку були одними з найважливіших ініціатив цього періоду. Занедбану територію колишнього цвинтаря місто почало впорядковувати лише в середині 1870-х років з ініціативи старости Станіслава Нємчиновського (1887-1891) - січневого повстанця, президента Ремісничої палати, майстра-кравця та депутата міської ради Львова. Проект був замовлений Арнольду Рьорінгу, інспектору міських садів. Розташований у південній частині міста "на площі 83 морги [за іншими даними - 86 моргів - ABR], пересіченій глибокими ярами і домінованій високими пагорбами", парк став окрасою міста. Його одноповерхова частина була побудована на місці колишнього Стрийського цвинтаря, заснованого у 1784 році, але функціонував він лише до 1823 року, коли на теперішній вулиці Стрийській було створено новий цвинтар. Францішек Яворський писав у 1910 році у своїй праці " Львів старий і вчорашній":

"Двадцять років тому на цьому місці була романтична порожнеча, непрохідний клубок ярів, балок, глиняних дюн, середовище проживання всіляких волоцюг, а іноді й аудиторія для скандалів кровожерливої молоді, яка без жодного нагляду старших вправлялася у стрільбі з вогнепальної зброї та влаштовувала свої улюблені ігри в "жандарма і розбійника". Покинутий австрійський форт був єдиним слідом людської руки. Лише за кілька років до Національної виставки 1894 року магістрат почав заліснювати пустку, а решту зробила сама виставка".

Проект парку передбачав закладання центральної грабової алеї, створення штучної водойми, численні посадки листяних, хвойних дерев та декоративних кущів. У 1888 році міський лікар д-р Антоній Павліковський у своїй доповіді "Про санітарні відносини у місті Львові" так писав про значення парку:

"З гігієнічного погляду парк Кілінських має для Львова неабияке значення, оскільки деревний покрив цього парку складається переважно з хвойних дерев (близько 35 тис. дерев), які, коли виростуть у більші дерева, будуть виділяти багато смолистих пахощів. Здорове і чисте повітря з полів і луків, якими оточений парк, заохочує громадськість відвідувати його у великій кількості і вже робить його найпопулярнішим місцем для прогулянок. [...] Оскільки вулецькі землі сприятливі для вирощування соснових дерев, такі дерева тут будуть вирощуватися, і цього року ними вже засаджено значну площу. У парку Кілінського є багато видів місцевих та екзотичних дерев і кущів, які незабаром будуть позначені табличками, щоб ознайомити громадськість, а особливо молодь, з номенклатурою деревних рослин, заохочуючи таким чином любов до природознавства".

У парку висаджено близько 40 000 дерев, серед яких численні клени, карликові каштани, вільхи, буки, берези, кілька видів дубів, акації, верби, горобини та липи. З хвойних дерев і кущів були сосни, ялини, канадські ялинки, кипариси, кедри, ялівці, тиси і модрини. Декоративні кущі включали червоне дерево, білий кизил, червону ліщину, глід, карагану, оливу, крушину, бузину та жасмин. Коли у 1894 році відкрилася Всесвітня виставка, яку відвідали сотні тисяч людей, Львівський міський павільйон, збудований за проектом Юліуша Гохбергера з виставки, згодом перенесли до парку і відкрили там ресторан, де влітку можна було посидіти з музикою. Натовпи львів'ян приходили сюди на прогулянки, а взимку схили використовували для катання на лижах і санчатах. У 1925 році Мечислав Орлович, знавець пам'яток і популяризатор туризму, писав про парк наступне: "Його рельєф - це гірські схили кількох ярів, вкриті мальовничими групами дерев з квітниками, штучними руїнами замку, ставком і рестораном [...]". Вищезгадані руїни були створені із залишків колишнього мосту, кам'яних межових стовпчиків і... надгробків зі старого цвинтаря. Ставок у парку досі існує і залишається одним з улюблених місць львів'ян, які приходять сюди з дітьми, щоб погодувати лебедів, порибалити та відпочити на лавочках, розташованих поруч.

Період Першої світової війни та подальша війна з більшовиками принесли втрати і руйнування всьому місту, в тому числі і міським паркам. Під час бойових дій на парк впав австрійський літак, а в листопаді 1918 року в парку були поховані загиблі українські стрільці, ексгумовані після війни і перенесені на Янівський цвинтар. Єжи Бандровський писав у 1921 році:

"Парк Кілінських і площа Повистава перетворилися на поле бою, де ворожі стрілецькі ланцюги билися один з одним. У цьому приємному куточку Львова, як і в усьому Львові, лунали гвинтівкові постріли, а площа Повітовий була тоді полем бою. Мабуть, тоді тут було дуже сумно... Порожнеча і безлисті, голі гілки дерев.... Осінній морок, сірість, холод, гвинтівкові постріли і ця скорботна трагедія".

У 1922 році преса повідомляла, що пам'ятники в парку розвалюються, а через знищення зелених насаджень вандалами у 1924 році навіть планували обнести газони колючим дротом. На щастя, після війни знайшлися гроші, щоб привести парк до ладу, і в 1922 році тут навіть з'явився лижний трамплін, на якому проводили чемпіонати Львова. Влітку 1924 року було впорядковано нижню паркову терасу, і парк перетворився на справжню окрасу міста. Магістрат також придбав нові лавки та урни.

Варто також пояснити походження колишньої назви парку. Вона була на честь полковника армії Костюшка Яна Кілінського (1760-1819), шевця за фахом. Завдяки щедрості місцевих мешканців у нижній частині парку було встановлено пам'ятник роботи львівського скульптора Юліана Марковського. Історія самого пам'ятника надзвичайно цікава. Після того, як міська влада затвердила гіпсову модель пам'ятника, до парку привезли величезний необроблений валун розміром 5 Х 5 м, який доставили до місця призначення на возі, запряженому вісьмома парами волів. Отримавши кошти на роботу, Марковський з помічниками приступив до обробки каменю, та оскільки він розпочав її лише у 1892 році, завершити скульптуру, як планувалося, тобто до відкриття Всесвітньої виставки, яке припало на річницю повстання Костюшка (1894 рік), не вдалося. Статуя була встановлена на п'єдестал лише восени 1895 року - і від самого початку викликала низку суперечок. Постать Кілінського була зображена в повний зріст, полковник тримав шаблю в правій руці, а в лівій - знамено. Мистецтвознавці та експерти вважали пам'ятник застарілим за формою і занадто помпезним за виразом. Корнель Макушинський нарікав у 1921 році: "Жахливий пам'ятник героїчному шевцю: певно, що Кілінський шив кращі чоботи, ніж скульптор, який осквернив його скульптурою". Тим не менше, пам'ятник став символом патріотизму для мешканців міста, і понад століття був мовчазним свідком історичних змін та політичних потрясінь. Пощастило, що пошкоджений пам'ятник вдалося врятувати за радянських часів, чому посприяло надзвичайно "правильне" - зрештою, пролетарське - походження Кілінського. На початку 21-го століття скульптурі бракувало двох найважливіших атрибутів - шаблі та прапора, а також частини табличок з написами. У 2006 році за кошти Міністерства культури і національної спадщини Польщі було проведено комплексну реставрацію пам'ятника, а також роботи з консервації та очищення території навколо скульптури. Роботи виконувала польсько-українська група консерваторів під керівництвом професора Варшавської академії мистецтв Януша Смази.

У 20 столітті парк зазнав численних реконструкцій та оновлень. У 1930 році тут збудували радіовежу, а в 1951 році частково розібрали вузькоколійку і створили на її місці Львівську дитячу залізницю. Через рік паркова брама з боку вулиці Паркової отримала декоративні арки на коринфських колонах за проектом Генрика Швецького-Вінецького. Територія парку була значно розширена за рахунок прилеглого пустиря, висаджено нові дерева. Всю територію обгородили парканом, а палац мистецтв і ротонду перетворили на спортивні споруди. Частину парку також відвели під дитячі майданчики. Сьогодні площа Стрийського парку становить 52 га і поділяється на три частини: нижню терасу (парк), верхню терасу та лісопарк. З моменту свого створення він був одним з найчарівніших місць у Львові, і залишається таким донині. Львів'яни із задоволенням годують лебедів, прогулюються руїнами та оглядають оранжерею, діти граються на дитячих майданчиках та біля фонтанів з казковими персонажами, а молодь користується першим в Україні скейт-парком, збудованим у 2008 році. У 2009 році за кошти польського уряду було відреставровано пам'ятник Кілінському, реконструйовано алеї та модернізовано освітлення. У 2013 році було відремонтовано фонтан з образом хлопчика з популярної української казки Івасика-Телесика, розташований біля головної брами з боку Паркової вулиці.

"Втім, про післявиставкову площу та парк Кілінського варто буде згадати хіба що майбутньому літописцю Львова. Занадто багато життя вирує там сьогодні, занадто часто її описують репортери і фейлетони, занадто багато закоханих пар гуляють там, і занадто часто всі елегантні львів'яни обирають проводити час саме там [...]", - писав Францішек Яворський у 1910 році. Через понад сто років після цих слів можна з упевненістю сказати, що Стрийський парк, безумовно, створив спогади для кількох поколінь львів'ян. І хочеться сподіватися, що він залишиться таким місцем для багатьох наступних.