В мае 1942 года Крым пришлось оставить. На Тамани на базе 72-й кавдивизии была сформирована 40-я отдельная мотострелковая бригада. Командиром был назначен генерал Н. Ф. Цепляев, начальником штаба — полковник Балдынов, начальником оперативного отделения — капитан В. И. Петров.
В составе только что рожденной бригады Алексей Кошелев участвовал в жарких боях в районе Краснодара, вскоре был назначен командиром пулеметной роты.
Как-то на одной из скалистых высот близ Туапсе закрепились два стрелковых взвода и пулеметчики лейтенанта Кошелева.
Четверо суток почти непрерывно шли бои за ту высоту. В промежутках между яростными атаками фашисты бомбили ее с воздуха, обстреливали артиллерией и минометами. Около тридцати раз пытались они сбросить наших воинов с вершины, но бесполезно. Защитники высоты не отступили ни на шаг.
Когда вышли из строя все офицеры оборонявшейся стрелковой роты, лейтенант Кошелев принял командование на себя, ввел в бой пулеметный резерв и снова обратил фашистов в бегство.
На четвертый день гитлеровцы, собравшись с новыми силами, полезли в решающую атаку.
Кошелев сам лег за пулемет, уничтожил несколько десятков гитлеровцев, рядом с ним разорвалась мина, но, и раненный, он продолжал стрелять. Не прекратил огонь и тогда, когда разрывная пуля попала в бедро. К Алексею подбежала санинструктор Фатима Додоева и ужаснулась: он был весь в крови. Пыталась сделать перевязку, да где там — лейтенанта от пулемета было не оторвать...
Осталось в роте восемь человек, четверо из них — ранены, в том числе и Кошелев. Радист старший сержант А. Шелест оставил рацию ротному, а сам с тремя солдатами перебегал по траншее, с места на место, и вел огонь с разных позиций — пусть думают фашисты, что людей на высоте еще много... Но вражеские атаки не ослабевали.
Фатима рассказывала потом, что видела, как лейтенант положил рядом с собой последнюю гранату. Догадалась, зачем.
И вдруг с левого фланга донеслось родное, русское «ура!». Это пришел на выручку комсорг батальона старший сержант Тихон Ламко с группой бойцов. И снова гитлеровцы вынуждены были бежать.
Увидел это Кошелев и упал без сознания. Только тогда Фатима Додоева вместе с бойцами смогла вынести Алексея в укрытие. Фатима... Будущая его любовь, верная и беззаветная, на всю жизнь.
Через некоторое время снова вернулся Кошелев в свою бригаду, освобождал Краснодар.
За мужество и героизм Кошелев был награжден орденом Красного Знамени. И вручил лейтенанту орден командующий армией генерал А. А. Гречко, навестив храброго и умелого командира в госпитале.