Неожиданная возможность предпринять большое путешествие в Африку прервала практические занятия Альфреда. Организатор экспедиции барон Джон фон Мюллер — большой любитель природы и известный охотник, пригласил участвовать в ней молодого Брема, узнав, что восемнадцатилетний сын сельского пастора хорошо подготовлен в орнитологии и препарировании птиц. Брем с восторгом принял предложение, отец также с удовольствием согласился на это путешествие сына.
Брем и Мюллер сели на корабль в Триесте 6 июля 1847 года. Тогда еще Альфред не думал, что увидит родные леса только через пять лет. Спутники приехали в Каир и задержались в этом городе, так как оба, из-за неосторожности, получили тепловой удар. Кроме того, они пережили ужасы землетрясения, которое произошло там как раз во время их пребывания.
В Каире барон решил расширить маршрут своей экспедиции, не ограничиваться только Египтом, а добраться до столицы Судана Хартума. Но только 28 сентября путешественники смогли отправиться в путь, присоединившись к партии католических миссионеров. Сообща наняли барку и поплыли вверх по Нилу. Барка продвигалась медленно, поэтому натуралисты имели возможность проводить много времени на берегу, охотясь за редкими животными и наблюдая природу. Четвертого января 1848 года они достигли лесистой и богатой водами части Судана, там собрали богатую коллекцию редких птиц, в том числе марабу, маленького черного журавля и других.
Шестого января путешественники прибыли в Хартум, где и прожили до 25 февраля. Охотились в окрестностях, знакомились с бытом населения, как местного, так и пришлого — турками, египтянами, европейцами. Дичь здесь была в изобилии, особенно в лесах, окружающих Голубой Нил, куда Брем отправился на довольно продолжительное время. Но вскоре заболел местной лихорадкой, приступы которой почувствовал еще на Ниле, и вернулся в Хартум. Подлечившись, Альфред снова отправился в леса и привез оттуда до 130 птичьих шкур.
В Хартуме Брему и Мюллеру представился благоприятный случай, они смогли присоединиться к опытному путешественнику английскому геологу Петерику и проехать частью водой, частью на верблюдах в малоизвестную страну Кордофан, лежащую в зоне саванн. Сначала отправились по Белому Нилу, потом начали сухопутное путешествие по жаркому Кордофану. Пребывание в этой стране было в высшей степени интересно, путешественники первый раз в жизни совсем близко наблюдали крупных млекопитающих: львов, леопардов, гиен. Их коллекция птиц пополнилась разными видами орлов, соколов, грифов. Но через четыре месяца убийственный климат заставил вернуться в Хартум. На обратном пути, проезжая по пустыне на спине верблюда, Брем претерпевал такие страшные страдания, что ежеминутно ожидал смерти. Наконец они достигли Нила и пошли на небольшом судне до Хартума, где намеревались довольно долго прожить, чтобы отдохнуть и вылечиться от лихорадки.
Альфред Эдмунд Брем
Мюллер и Брем прожили в Хартуме до 28 августа, а потом пустились в обратный путь вниз по Нилу. Генерал-губернатор Хартума отдал в их распоряжение две барки, на которых поместились многочисленные ящики с коллекциями и большое число клеток с животными. 28 октября доехали до Каира, довольные тем, что вернулись целыми и невредимыми из трудного путешествия и довезли в сохранности все собранные сокровища. Конец года они прожили в этом городе, делали небольшие экскурсии по окрестностям для охоты и дополнения своих коллекций.
29 января барон фон Мюллер отплыл из Александрии в Европу, с тем чтобы начать подготовку новой, гораздо более обширной африканской экспедиции. Брем остался в Египте. Почти год находился он то в Каире, то в Александрии, дожидаясь барона или хотя бы денег от него на предварительные работы по организации экспедиции.
Впрочем, любознательный юноша не терял времени даром. Он, облачившись в турецкий костюм, охотился в дельте Нила, бродил по Каиру, знакомился с его памятниками древности и бытом городского населения. Более того, пригласив опытного учителя, систематически изучал под его руководством арабский язык и переводил священную книгу мусульман — Коран.
Тем временем Мюллер добывал средства для экспедиции и вербовал новых членов. Экспедиция была задумана в грандиозных масштабах. Предполагалось добраться Красным морем до Суакина, доехать на верблюдах до Хартума, а оттуда подняться по Нилу до области проживания негров бари, то есть до 4-го градуса северной широты. После более или менее продолжительного пребывания среди них экспедиция должна была повернуть на запад к Атлантическому океану.