В октябре 1920 г. Г. Н. Косенко был послан делегатом на 3-й съезд Российского комитета союза молодежи (РКСМ) в Москву, где слушал знаменитое выступление В. И. Ленина «Задачи союзов молодежи». Вернувшись в Ставрополь, летом 1921 г. Георгий был принят в ряды ВКП(б) и переведен на должность военного цензора в Ставропольскую губернскую ЧК. До начала 1922 г. «чрезвычайка» прифронтового Ставрополья играла второстепенную роль по сравнению с особыми отделами частей РККА, воевавших в регионе против остатков белой армии Врангеля, «зеленых» партизан-махновцев и горских сепаратистов. За два года в губЧК Ставрополья сменились двенадцать председателей. И лишь возглавивший ее в апреле 1922 г. 29-летний ветеран ВЧК С. М. Штыб, ранее выполнявший особые задания Ф. Э. Дзержинского по организации чекистской работы в Дагестане, Азербайджане и Екатеринбурге, сумел наладить ее и на Ставрополье с помощью таких местных помощников, как Г. Н. Косенко.

За год работы в регионе Штыб разгромил крупную банду бывшего есаула царской армии Л. Конырева-Конара, и вслед за объявленной ВЦИК в марте 1923 г. амнистии к пятой годовщине Октября принудил сложить оружие и вернуться к мирному труду повстанцев из отрядов полковников Комарова и Беззубова.

За выдающиеся успехи по установлению порядка на Северном Кавказе С. М. Штыб в апреле 1923 г. был награжден орденом Красного Знамени, а в июне года переведен с повышением на должность начальника Горского отдела ОГПУ во Владикавказе. 23 ноября 1923 г. Штыб и его адъютант И. Котов погибли в жестоком бою с бандитами в пригороде Владикавказа. В память о бесстрашном чекисте с 1926 г. его имя носит бывшая Краснорядская площадь Владикавказа, на которой с 1987 г. стоит памятник С. М. Штыбу.

В феврале 1923 г. 20-летний Г. Н. Косенко по ходатайству С. М. Штыба получил свою первую боевую награду – именной револьвер «Наган» от Ставропольского губисполкома и губернского отдела ГПУ. А в июле 1924 г. начальник Секретного отдела Ставропольского окружного отдела ОГПУ Г. Н. Косенко был переведен в Сочи на должность начальника контрразведывательного отделения Черноморского окружного отдела ОГПУ. Это назначение состоялось с подачи сменившего Штыба на посту начальника Ставропольского губотдела ОГПУ бывшего латышского стрелка, коммуниста с 1914 г. О. Я. Нодева. В 1919–1921 гг. Нодев участвовал в организации погранохраны в Псковской области и в Карелии. Получив весной 1924 г. задачу по укреплению государственной границы СССР на прибрежном участке между Сочи и Новороссийском, Нодев привлек к ее решению местных чекистов, хорошо знавших специфику северокавказского региона, включая Косенко.