Історія нашого навчального закладу розпочалася ще у далекому 1880 році. Саме 1 листопада 1880 року у Києві був створений приватний навчальний заклад, який уже в серпні 1884 року отримує права «Правительственого училища» з розміщенням у Києві на Іринінському прозді – нині це Іринінська вулиця – у будинку № 4 у найманому приміщенні.
У Державному архіві м. Києва збереглося «Дело Киевской городской управы хозяйственного отделения с ходатайствами об отводе участка земли под устройство городского училища имени Н.В.Гоголя». Звіряючи архівні джерела, було встановлено, що саме під час відзначення у Києві 50-річчя з дня смерті М.Гоголя Київською міською Думою було прийняте рішення увіковічнити його пам'ять, збудувавши нову гімназію, і назвати її іменем славетного письменника.
А уже у 1904 році Київське урядове училище ім. М.В. Гоголя продовжує роботу у новому приміщенні, збудованому за проектом відомого архітектора Іполіта Володимировича Ніколаєва, автора проектів київського театру «Шато де фльор», Покровської церкви, корпусів Олександрівської міської лікарні, будинків на вул. Хрещатик, Некрасовській, Богдана Хмельницького та Лук’янівській.
Будівля на вул. Предславинській 30-а, де розташована гімназія № 56, і нині є окрасою Києва і пам’яткою архітектури. Саме з 1904 року «Новое строение», як тоді кияни називали нову будівлю училища, стає осередком міської освіти, з яким пов’язані імена прогресивних вітчизняних педагогів кінця ХІХ – початку ХХ століття Т.Г.Лубенця та С. Ф.Русової.
Восьмирічна школа для дівчат (з 1918 р.), середня загальноосвітня школа № 56 для дівчат (з 1936 р.), середня загальноосвітня школа № 56, середня загальноосвітня школа з поглибленим вивченням англійської мови з 1 класу (з 1975 р.), з 1991 року – школа-гімназія, з 1996 – державний заклад освіти – гімназія № 56. З З 2012 року навчальний заклад продовжує свою діяльність шляхом як Предславинська гімназія № 56. З 1979 року навчальний заклад очолює Д.І.Петренко.
