Окончив академию, Кюи был оставлен преподавателем топографии с производством «за отличные успехи в науках в поручики». Началась многотрудная педагогическая и научная деятельность Кюи, требовавшая от него огромных усилий и продолжавшаяся до самого конца жизни. За первые 20 лет службы Кюи прошел путь от прапорщика до полковника. Как-то раз его пригласили прочесть в Академии Генерального Штаба курс лекций по инженерному делу. Планировалось четыре лекции, но отчего-то в плане, представленном в академию, Кюи обозначил только три лекции и их темы. Тогда начальник академии генерал Драгомиров своей рукой добавил в план четвертую лекцию, а в качестве темы обозначил: "Влияние музыки на инженерное искусство на примере осады Иерихона" (как вы помните из Библии, стены крепости обрушились оттого, что осаждавшие стали громко трубить). Публикацией в 1878 году в «Инженерном журнале» блестящей статьи Кюи выдвинулся в число наиболее видных специалистов в области фортификации. Вскоре он стал профессором академии и был произведен в генерал-майоры. Кюи — автор целого ряда значительных работ по фортификации, учебников, по которым училось едва ли не большинство офицеров русской армии. В дальнейшем он дошел до высшего чина инженерных войск — инженер-генерала, занимался педагогической работой также в Михайловской артиллерийской академии и академии Генерального штаба.
Репин. Портрет Ц.А.Кюи
19 октября 1858 года Кюи женился на Мальвине Рафаиловне Бамберг (1836–1899), ученице Даргомыжского. Ей посвящено оркестровое скерцо, с главной темой, В, А, В, Е, G (буквы её фамилии) и упорным проведением нот С, С (Cesar Cui) — идея, явно навеянная Шуманом, имевшим вообще большое влияние на Кюи. Исполнение этого скерцо в Петербурге в симфоническом концерте Императорского Русского Музыкального Общества 14 декабря 1859 года было публичным дебютом Кюи как композитора.
М. Р. Кюи
К тому же времени относятся два фортепианных скерцо и первый опыт в оперной форме: два акта оперы «Кавказский пленник» (1857–1858), позже переделанной в трёхактную и поставленную в 1883 году на сцене Мариинского театра в Петербурге, и в Москве.
В 1885 году в городе Льеже прошла премьера «Кавказского пленника» — это была первая русская постановка на бельгийской сцене. В Бельгии Цезарь Кюи написал оперу «Флибустьер» по лирической комедии Жана Ришпена. Ее поставили спустя несколько лет на сцене парижской Комической оперы. После премьеры Цезаря Кюи избрали членом-корреспондентом «Института Франции» и наградили Командорским крестом ордена Почетного легиона.
В эти годы Цезарь Кюи писал оперу «Вильям Ратклиф» по произведению Генриха Гейне. Композитор вспоминал, что трагедия в поэтическом переводе Алексея Плещеева привлекла его фантастичным сюжетом, а также красотой стиха: «Красивый стих всегда меня прельщал и имел несомненное влияние на мою музыку». Премьера оперы прошла в 1869 году в Мариинском театре. Музыкальный критик Владимир Стасов назвал ее «созданием, полным таланта, увлечения, страсти, оригинальности, мастерства», лучшей оперой после произведений Михаила Глинки и Александра Даргомыжского.
Тогда же написана одноактная комическая опера в лёгком жанре «Сын Мандарина» (1859), поставленная на домашнем спектакле у Кюи при участии самого автора, его жены и Мусоргского, причем увертюра была сыграна Кюи и Балакиревым в 4 руки. Публично опера была исполнена в Клубе художников в Петербурге (1878). Пройдет много лет, и эти произведения станут наиболее репертуарными операми Кюи.
В 1876 г. в Мариинском театре состоялась премьера новой работы Кюи — оперы «Анджело» на сюжет драмы В. Гюго (действие происходит в XVI в. в Италии). К ее созданию Кюи приступил будучи уже зрелым художником. Его композиторское дарование развилось и окрепло, значительно возросло техническое мастерство. Музыка «Анджело» отмечена большим вдохновением и страстностью. Созданы характеры сильные, яркие, запоминающиеся. Кюи умело построил музыкальную драматургию оперы, постепенно от действия к действию усиливая разнообразными художественными средствами напряжение происходящего на сцене. Он мастерски применил речитативы, насыщенные экспрессией и богатые по тематическому развитию.