6 июля 1979 года банда выехала из Майкопа в Ставропольский край и возле города Невинномысска совершила нападение на автомашину "ВАЗ-2103", в которой находились трое мужчин. Всех троих в упор расстреляли, отвезли к Армавиру и там зарыли в землю. Одним из убитых оказался инспектор ГАИ, и его форма была взята бандитами для совершения последующих преступлений. И они не заставили себя долго ждать.
29 июня того же года братья Самойленко напали на детский сад в Ставрополе, убили сторожа и похитили предметов (пишущая машинка, ковры) на сумму 2800 рублей. На эти деньги у некоего Лупенникова, приятеля Юрия, братья приобрели два пистолета системы "беретта". Дальше преступления пошли как по маслу. 19 августа на трассе Ростов - Краснодар бандиты подстерегли автомашину "ВАЗ-2106", убили еe владельца и взяли автомобиль, магнитофон и другие вещи. Через 11 дней - новое, еще более страшное преступление. На той же трассе Ростов - Краснодар братья расправились с семьей Ивановых - отцом, матерью и их одиннадцатилетней дочкой. Улов, за который лишили жизни целую семью, был небогат: посуда, одеяло, бусы, надувные матрасы, столик и три складных стула. А Дмитрий, пользуясь пассатижами, извлек у отца семейства золотые коронки изо рта.
12 сентября на трассе Ростов - Баку братья Самойленко (Дмитрий, как всегда, был в форме инспектора ГАИ) остановили очередную машину и хладнокровно застрелили ее хозяина. И у этого несчастного Дмитрий вырвал золотые коронки.
15 сентября в районе Большого Ставропольского оросительного канала они совершили налет на автомашину, в которой находились два жителя города Ташкента. Пассажиры были убиты и закопаны в ближайшей лесополосе.
11 октября на трассе Ростов - Баку братья остановили "жигули", которыми управлял житель города Харькова Айрапетян. Его постигла та же участь, что и всех остальных. Однако во время этого нападения пострадал и Дмитрий: смертельно раненный Айрапетян рванул свою машину вперед и сбил старшего из братьев с ног. В результате тот повредил себе лицо. Пришлось в спешке покидать место преступления и в Майкопе положить Дмитрия в больницу. Находился он в ней около десяти дней под фамилией Карпенко. Пока главарь банды лечился, младшие братья отдыхали от убийств в своих семьях. Дома их ломились от награбленного добра, и жены на все это смотрели сквозь пальцы. Ни одна из них так и не поинтересовалась, откуда взялись у них все эти предметы.
Как только раны на лице Дмитрия затянулись, бандиты вновь вышли на большую дорогу. Теперь они намеревались напасть на инкассатора колхоза имени Ворошилова, который 13 ноября 1979 года должен был получить крупную сумму денег в банке. Для осуществления этого преступления братьям требовалась машина, которую решено было получить старым испытанным способом.
12 ноября на трассе Ростов - Баку братья напали на автомобиль "жигули" и застрелили ее хозяина. Однако дальше случилась незадача: оставленная на ночь у гостиницы "Кубань" в Невинномысске машина была разграблена и искорежена местными грабителями. Но Самойленко не сильно горевали. 13 ноября они выехали на свою привычную трассу и через несколько минут застрелили еще одного владельца "жигулей". Теперь у братьев была машина для ограбления инкассатора. Однако через несколько минут после ее захвата выяснилось, что это не самое лучшее техническое обеспечение банды. Проезжая через Ставрополь, бандиты увидели впереди себя двигавшийся в сторону Изобильного многотонный грузовик "урал-377". Дмитрий сразу смекнул, что таким "танком" можно легко протаранить колхозный "газик" с кассиром и охраной. Поэтому, обогнав грузовик, бандиты остановили его на безлюдном шоссе и спокойно расстреляли двух сидевших в кабине мужчин. Пересев в грузовик, братья тронулись в дальнейший путь. Но удача покинула их. В тот день колхозный "газик" с деньгами оказался намного расторопнее многотонного грузовика и, обогнав его на скорости, скрылся из вида. Налет не состоялся.
Неудача с колхозным кассиром подстегивала их на все новые и новые преступления. До конца года они лишили жизни еще более десяти ни в чем не повинных людей. В частности, 20 декабря в Ставрополе убили владельца новенькой "нивы", а 30 декабря там же лишили жизни парня, который на вещевом рынке продал им ковер "Русская красавица", после чего сел к братьям в машину, чтобы привезти их к себе домой за вторым ковром.
В начале 1980 года братья по совету Дмитрия решили несколько "перепрофилироваться" и заняться квартирными кражами. 4 января они ограбили квартиру в Ставрополе, но "навар" составил около двух тысяч рублей. Однако эта неудача не очень обескуражила братьев, и 15 января они влезли в еще одну квартиру (теперь уже по наводке старого приятеля Лупенникова. Фамилия изменена) и унесли добра намного больше, чем из первой. Все это они увезли в Майкоп и поделили между собой.
В промежутке между этими двумя ограблениями 7 января братья вновь вышли на "тропу" дорожного бандитизма на трассе Краснодар - Ростов. Там на участке между Выселками и Тихорецком они напали на машину некоего Арзамасцева, который поздно ночью из аэропорта в Краснодаре подвозил пассажира в село Белая Глина. Позднего пассажира Самойленко убили, а вот с хозяином машины произошла осечка: раненный в ногу Арзамасцев сумел скрыться от бандитов. Именно этот человек и станет для милиции единственной ниточкой, которая протянется к братьям. Уголовное дело по этому нападению затребуется сначала в Краснодар, а затем в Ставрополь. А через несколько дней выяснится, что это нападение не единственное в послужном списке банды. При спуске воды из Невинномысского оросительного канала на его дне было найдено шесть автомашин марки "жигули", в которых были обнаружены точно такие же гильзы, что и в случае с Арзамасцевым. Перед следствием впервые начала приоткрываться страшная личина неуловимых убийц.