Наконец 25 сентября последовал долгожданный приказ о начале операций. Лангсдорф избрал первым районом действий северо-восток Бразилии около порта Ресифи. 27 сентября он отпустил «Альтмарк», а спустя 3 дня ему подвернулась первая жертва. Правда, первый блин чуть было не вышел комом: обнаруженный британский пароход «Клемент» (5051 брт) пустился наутек, радируя об атаке. Когда же его удалось остановить, выяснилось, что транспорт совершал каботажный рейс из Пернамбуко в Баию с маловажным грузом. Попытка потопить его превратилась в настоящий фарс: несмотря на открытые кингстоны и заложенные немцами заряды, «Клемент» упорно не желал тонуть. Пришлось выпустить в него 2 торпеды, и обе прошли мимо! В конце концов заработали 150-мм пушки и пароход отправился на дно. Лангсдорф проявил себя истинным джентльменом, связавшись с радиостанцией "Каста Луэго" в Пернамбуко и сообщив координаты английских шлюпок, хотя тем самым обнаруживал свое местоположение. Капитан и старший механик «Клемента» заняли место узников в импровизированной «камере» на борту «Шпее», став первыми, но далеко не последними ее обитателями. Впрочем, в тот же день немцы остановили греческий пароход «Папаленос» и после досмотра передали на него пленников. Так желание во всем следовать правилам «мягкой» крейсерской войны привело к быстрой идентификации рейдера, поскольку английские моряки немедленно сообщили о случившемся. Единственное, что удалось сделать Лангсдорфу для дезинформации, — это вывесить фальшивую доску с названием «Дойчланд», в результате чего союзники долгое время, вплоть до Ла-Платы, как бы "поменяли местами" оба "карманных линкора". Выгода от такой мистификации была более чем сомнительной. Реакция последовала очень быстро. Для операций против рейдеров (в середине октября союзники узнали, что в океане действуют два немецких "броненосца") было выделено 8 тактических боевых групп, в состав которых номинально вошли 3 линейных крейсера — английский «Ринаун», французские «Дюнкерк» и «Страсбург», авианосцы "Арк Ройял", «Гермес» и «Беарн», 9 тяжелых и 5 легких крейсеров, не считая десятков других боевых единиц (вплоть до линкоров), охранявших трансатлантические конвои. Однако фактически против «Шеера» оперировало не так много кораблей. В Южной Атлантике находились 3 британских соединения: крейсерская эскадра под командованием коммодора Хэрвуда (группа "G"), прикрывавшая южноамериканские воды (тяжелые крейсера «Эксетер» и "Камберленд"), группа «H», базировавшаяся на Кейптаун (тяжелые крейсера «Сассекс» и "Шропшир"), группа «К» под командованием контр-адмирала Уэллса, наиболее сильная из всех (линейный крейсер «Ринаун» и авианосец "Арк Ройял").
Вторую жертву "карманный линкор" нашел на линии Кейптаун — Фритаун 5 октября. Британский пароход "Ньютон Бич" (4651 брт), перевозивший 7200 т маиса, едва успел дать сигнал об атаке, как призовая партия захватила его. Здесь немцев ждала ценная добыча: из доставшихся документов удалось составить достаточно полное впечатление о системе радиопереговоров с торговыми судами и даже получить в исправном виде стандартную английскую рацию, снятую с судна и установленную в рубке "Графа Шпее". Ценный трофей было жалко топить, и "Ньютон Бич" под управлением немецких моряков сопровождал рейдер.
Спустя два дня последовал новый успех. Еще один «британец» — пароход «Эшли» (4222 рег. т), перевозивший в Англию сахар-сырец, отправился на дно, а его команда перебралась на "Ньютон Бич" — правда, ненадолго. Теперь Лангсдорф находился на пересечении оживленных морских путей и не желал сковывать свои действия захваченным транспортом. "Ньютон Бич" последовал за «Эшли», а команды обоих судов оказались в гораздо менее комфортных условиях на борту рейдера.
Между тем пленники имели шанс пойти на дно вместе со своей "плавучей тюрьмой". Сигнал с "Ньютон Бич" был принят торговым судном и ретранслирован на крейсер «Камберленд». Если бы командир крейсера мог предположить, что сигнал не достигнет мощной радиостанции но Фритауне — координационном центре охоты за рейдерами в Южной Атлантике, он, конечно же, нарушил бы предписанное радиомолчание. Судьба «Шпее» и «Альтмарка» могла стать незавидной, поскольку во Фритаун следовала мощная группа «К» контр-адмирала Уэллса. Вероятность обнаружения немецких судов с воздуха в условиях хорошей погоды была высокой, а «Ринаун» и «Камберленд» могли бы легко справиться с "карманным линкором".
Тем не менее, 9 октября «Шпее» едва не лишился своего судна снабжения. В районе западнее островов Зеленого Мыса самолет с авианосца "Арк Ройял" заметил лежащий в дрейфе большой танкер. На запрос о принадлежности с него был получен ответ о том, что это американский транспорт «Делмар». Адмирал Уэллс засомневался. Однако, имея в своем распоряжении лишь линейный крейсер «Ринаун» и "Арк Ройял", он мог выбрать для досмотра подозрительного судна либо 30-тысячетонный гигант, либо еще менее подходящий авианосец, что в любом случае означало сотни тонн сожженной нефти и риск отвлечься от других задач ради скорее всего бесполезной проверки. Так «Альтмарку», выдававшему себя за «Делмар», удалось чудом ускользнуть, после чего он отправился на юг, в более пустынные районы. Если бы англичанам удалось потопить его, рейдерство «Шпее» могло прекратиться гораздо раньше.
В результате вместо успеха к англичанам пришла очередная неприятность. 10 октября "карманный линкор" остановил крупный транспорт «Хантсмэн» (8196 брт), перевозивший различные пищевые грузы, в том числе полторы тысячи тонн чая. Для его экипажа, составлявшего 84 человека, на борту рейдера не оказалось достаточно места, и приз пришлось оставить на плаву. Однако, чтобы спутать неприятелю карты, Лангсдорф приказал передать с захваченного на "Ньютон Бич" радиопередатчика сообщение о там, что он атакован подводной лодкой: это объясняло его исчезновение, не выдавая при этом присутствие надводного корабля. «Шпее» двинулся на юг, навстречу счастливо избежавшему гибели «Альтмарку». 14 октября на судно снабжения перегрузили пленных и захваченные на «Хантсмэне» продукты. Следующие 4 дня «броненосец» и танкер следовали рядом. Лангсдорф выжидал, анализируя перехваченные и частично дешифрованные радиограммы, сообщавшие о наличии в океане двух немецких линкоров и о мерах предосторожности для судов при сближении с неизвестными боевыми кораблями. Радиообмен дал командиру «Шпее» и его офицерам немало полезной информации — в частности, подсказал перекрасить свой самолет в цвета английского камуфляжа.
22 октября бортовой «Арадо» обнаружил крупный транспорт и вывел на него рейдер. После предупредительных залпов попытки радировать с судна об атаке прервались, и призовая партия высадилась на новехонький «Тривэниэн» (8835 брт), перевозивший цинковую руду из Австралии в Англию. Но радист сделал свое дело: через некоторое время служба радиоперехвата ("B-Dienst") сообщила, что о захвате уже знают в британской базе в Саймонстауне. Сигнал о бедствии принял также транспорт "Лэнстивен Касл", находившийся поблизости от места действия.
Второй раз Лангсдорф вывел свой корабль из-под удара. Взяв курс на запад и дав полный ход, «Шпее» затем резко повернул на юго-восток. Командир впервые рискнул связаться со штабом в Германии, предупредив, что собирается завершить крейсерство в январе 1940 года.
Индийский океан, в который теперь направлялся "Адмирал граф Шпее", также представлял собой тучное поле для рейдерства. Все следовавшие через него торговые пути пролегали либо к Суэцкому каналу, либо огибали мыс Доброй Надежды. Лангсдорф избрал зону южнее острова Мадагаскар, поскольку не хотел тащить за собой «Альтмарк», подвергая его риску быть обнаруженным у южной оконечности Африки. Удобная позиция в юго-восточном углу Индийского океана оставляла возможность для быстрого возврата в Атлантику и одновременно вызывала бы сильную головную боль у "владычицы морей", заставив ее расширить зону поиска на целый океан!
28 октября «Альтмарк» был отпущен, а 4 ноября «Шпее», по-прежнему никем не замеченный, обогнул мыс Доброй Надежды. Первая неделя крейсерства на новом месте оказалась бесплодной: океан оставался пустынным. Погода стала портиться, что привело к событию, имевшему важнейшие последствия. 9 ноября гидросамолет «Арадо-196», сослуживший рейдеру хорошую службу, потерпел аварию и надолго вышел из строя. "Карманный линкор" два раза пересек южный вход в Мозамбикский пролив, подойдя к самому побережью Африки — и все безуспешно. Только 14 ноября он остановил небольшой, но новый теплоход "Африка Шелл", следовавший в балласте и ставший единственной жертвой рейдера в Индийском океане. Правда, сам факт пребывания там немецкого рейдера продолжал сказываться на судоходстве (прежде всего британском) в течение еще долгого времени.
20 ноября «Шпее» обогнул южную оконечность Африки в обратном направлении. Плохая погода и безрезультатное крейсерство в опасных водах сильно измотали экипаж, поэтому возвращение в тропические широты и встреча с «Альт-марком», состоявшаяся 26 ноября, стали приятными событиями. Рейдер пополнил запас топлива и продовольствия, получив возможность находиться в море аж до конца февраля 1940 года. Правда, после трехмесячного плавания в тропиках днище требовало очистки, а дизели — профилактического ремонта. Пришлось заняться поочередной переборкой двигателей, на что ушло несколько дней. По окончании работ Лангсдорф после долгих раздумий решил вернуться в «счастливый» район между Фритауном и Рио-де-Жанейро, где пересекались морские пути, ведущие к Кейптауну из США и Европы. Авиамеханикам наконец-таки удалось кое-как наладить работу мотора корабельного «Арадо», и рейдер вновь обрел «глаза», но, как оказалось, ненадолго.
