До начала Восточной кампании полк оставался «безработным». Исключением оказался только 2 й батальон, который силами своей 5 й роты под командованием обер-лейтенанта Книше охранял Дунай и румынские нефтепромыслы. В это время оба офицера абвера Хиппель и Рудлеф возвратились в абвер-II, где им нашли другое применение. Командование 1 м батальоном принял майор Хайнц, 3 м — капитан Якоби. В октябре 1942 г. 800 й полк особого назначения был переименован в полк особого назначения «Бранденбург».
Пополнение батальонов шло так быстро, что уровень спецподготовки офицеров и солдат постоянно снижался. Стали все чаще проявляться признаки того, что полк уже не может достаточно эффективно выполнять свои первоначальные задачи. Причина этого состоит, по-видимому, в том, что офицерский корпус все больше терял опыт агентурно-боевых действий и все очевиднее переходил на методы и тактику пехоты. Возникло небрежение к инженерно-саперной подготовке. Тем не менее полк «Бранденбург» смог добиться значительных успехов. В Греции, например, часть 2 го батальона во главе с капитаном Якоби первой вошла 27 апреля 1941 г. в Афины, обеспечила охрану важнейших объектов и подняла германские флаги над зданиями городской управы и полицейского управления.
Летом 1941 г., когда группа армий «Север» продвигалась в Латвии, одно из подразделений «Бранденбурга» захватило мост через Двину (Даугаву) и предотвратило его подрыв. Солдаты этой группы были замаскированы под раненых красноармейцев и подъехали к мосту вместе с арьергардом отступавших советских войск. Достигнув моста, они внезапно напали на его охрану и овладели им. Благодаря этому продвижение немецких войск к Риге было осуществлено быстро и без потерь.
При наступлении на Львов в ночь на 29 июня 1941 г. роль передового отряда выполнял упомянутый выше батальон украинских националистов «Нахтигаль». Он действовал в составе 2 го батальона полка «Бранденбург». Их задачей было пробиться к центру города и захватить «Цитадель» вместе с основными транспортными и хозяйственными объектами города (электростанция, вокзал, радиостанция и др.). После того как сопротивление советских войск было сломлено еще на подступах к городу, в самом Львове серьезных боев не было. К 10 часам утра все намеченные объекты оказались в руках немцев. Хорошо знавшие местность украинские унтер-офицеры батальона сразу же после занятия города провели своих немецких офицеров к тюрьмам НКВД. Потому что по всему городу распространились слухи об убийстве нескольких десятков тысяч заключенных. Конечно, цифры явно завышены, но Советы действительно истребляли арестованных ими украинских интеллигентов-националистов. Их трупы были частично замурованы в подвалах, а частично облиты бензином и сожжены. Эта ужасающая находка тут же вызвала в городе и во всей Восточной Галиции кровавые акты возмездия, особенно со стороны тех украинцев, члены семей которых пали жертвами НКВД. Львов до позднего вечера 30 июня находился в полном распоряжении 1 го батальона полка «Бранденбург». «Акты мести, частично организованные, но большей частью носившие характер стихийных погромов, начались под вечер 30 июня, однако немецкие войска в них не участвовали. Возможно, кто-то из украинских солдат батальона «Нахтигаль» действительно участвовал в этом, но сейчас доказать это уже невозможно. Если это на самом деле имело место, то делалось вопреки строгому приказу. Как вышестоящий начальник я запретил всякие акты мести, а также — выполнение так называемого «приказа о комиссарах». Это сообщение подполковника Хайнца автору этих строк подтверждалось заявлениями и других свидетелей тех событий.
Когда подразделения батальона «Нахтигаль» овладели городской радиостанцией, молодые украинские унтер-офицеры в течение нескольких часов вещали из Львова от имени «Свободного украинского государства». Однако новое правительство во главе с Ярославом Стецько (официальный заместитель Бандеры) проработало всего одну неделю. Уже 5 июля оно было разогнано СД. Это был первый ущерб, причиненный добрым отношениям западноукраинских добровольцев и местного населения к немцам. Разочарование стало еще большим, когда части Западной Украины были включены в «Генерал-губернаторство Польша». 25 июля 1941 г. в Юзвин прибыл адмирал Канарис, чтобы вывести батальон с фронта. Лишь незначительная его часть продолжала еще некоторое время выполнять обязанности полицейской команды.
Начиная с 1942 г. под давлением обстановки на Восточном фронте батальоны полка «Бранденбург» все чаще использовались из тактических соображений как сугубо пехотные части. При этом они несли трудновосполнимые для таких войск потери. Но, когда они решали свойственные им задачи, они добивались больших успехов. Моторизованные разведдозоры полка покрывали сотни километров, ведя дальнюю разведку. Чтобы решать такие задачи, требовалась тщательная подготовка, которую осуществляли разведотделы штабов армий и групп армий. Некоторые операции планировались в самом полку. Иногда это были чистые импровизации. Так, на подступах к Кавказу одна из рот «Бранденбурга» присоединилась на захваченных ранее советских грузовиках к колонне отступающих советских войск, овладела важным мостом у Майкопа и обеспечила временный захват русских нефтепромыслов. Но такие вещи удавались далеко не всегда. «Однажды в ходе наступления на Кавказе нужно было предотвратить разрушение плотины русскими подрывниками. Одна из рот «Бранденбурга» подъехала к плотине на нескольких захваченных у русских грузовиках. Советский комиссар, осуществлявший контроль на шоссе, уже проверил первую машину, и сошедшие с нее люди, исполнявшие роль измученного боями русского арьергарда, стали снова залезать в свою машину, как вдруг комиссар заметил безучастно сидевшего на обочине «товарища» и что-то сказал ему по-русски. К сожалению, это был унтер-офицер из Гамбурга, ни слова не понимавший по-русски. Это увидел командир «бранденбуржцев» лейтенант барон Фёлькерзам, прибалтиец и потомок царского адмирала Фёлькерзама, погибшего в сражении при Цусиме… Собравшись с духом, он крикнул комиссару: «От него ничего не добьешься. Он армянин». И надо же было так случиться: комиссар заговорил с «армянином» на его «родном» языке. Ничего не оставалось, как нажать на спуск автомата по комиссару и этим дать сигнал к атаке. Несмотря на эту промашку, операция прошла успешно». В другой раз этому же подразделению удалось, переодевшись в русскую форму, осуществить рейд в глубокий тыл русских, разгромить штаб одной дивизии и возвратиться на свои позиции.