Вслед за тем предпринята была постройка самого здания, в котором должно было поместиться новое заведение, при чём граф далеко не ограничивался средствами, указанными на то в записке: не смотря на предварительно заготовленный материал, крепостной труд и разные пособия со стороны прилежащих к Нежину имений графа Безбородко, стоимость здания возросла до 604,034 рублей. Постройка столь обширного здания на болотистой нежинской почве, конечно, заняла много времени; встретились и другие затруднения замедлившие на целые пятнадцать лет открытие гимназии. Графу Илье Андреевичу не суждено было дождаться осуществления заветной мысли: он скончался 3-го июня 1816 года. Ближайший наследник его в мужской линии, пятнадцатилетний сын старшей дочери, граф Александр Григорьевич Кушелев-Безбородко, в то время ещё продолжал своё образование. Только в 1820 году 19-го апреля последовал Высочайший рескрипт, окончательно утвердивший высшее учебное заведение в Нежине, с назначением графа Александра Григорьевича почётным его попечителем, а по нём — всегда старшего в его роде. Проект устава гимназии высших наук составлен был ещё за год перед тем; но утверждение его также замедлилось слишком на пять лет, в следствие недоумений, возникших в главном правлении училищ, где он рассматривался: в проекте не было назначено окладов секретарю правления, кассиру, расходов на учебные пособия воспитанникам и прочее; кроме того, главное правление училищ признавало необходимым уделять часть доходов в пособие к содержанию преподавателей. Были, без сомнения, недоумения и относительно организации учебного дела, так как в след за тем были предлагаемы первому директору относящиеся сюда вопросы. Все эти недоумения своевременно сообщались почётному попечителю.
Не предвидя скорого их решения, граф обратился к министру с просьбой о дозволении открыть, впредь до утверждения устава, курс учения в гимназии. Разрешение было дано и в то же время предписано попечителю харьковского учебного округа распорядиться открытием гимназии.
К тому же времени удалось приискать и вполне достойного директора гимназии. Замечательно, что первые два директора и, притом, лучшие, Кукольник и Орлай, были карпато-руссы. Последний, раньше переселившийся в Россию и успевший скоро обратить на себя внимание высшей медицинской администрации, указал на Кукольника, как достойного кандидата на одну из кафедр при С.-Петербургском Педагогическом Институте. Назначенный профессором римского права, он в то же время читал студентам химию, технологию и сельское хозяйство, а в открытых после публичных курсах для чиновников — физику, римское право и частное русское право. Серьёзное отношение Кукольника к своему делу выразилось рядом печатных курсов по наибольшей части упомянутых предметов, что и доставило ему весьма почётную известность. В 1813 году он назначен был преподавателем римского и гражданского русского права великим
