7 июля 1968 года, спустя восемь месяцев после ухода Джеффа Бека, окончательно распалась группа The Yardbirds. Джимми Пейдж, у которого остались как права на название коллектива, так и концертные обязательства, начал при поддержке менеджера Питера Гранта, до этого также работавшего с Yardbirds, подбирать новый состав музыкантов. Первым приглашённым стал Джон Пол Джонс, бас-гитарист, клавишник и аранжировщик, к тому времени уже имевший богатый опыт студийного сотрудничества со многими известными исполнителями (включая The Yardbirds). Он прочёл статью в журнале Disc и по совету жены тут же позвонил Пейджу.

Первый кандидат на роль вокалиста, Терри Рид (как выяснилось, уже связанный контрактом с менеджером Микки Мо́стом), порекомендовал Пейджу обратить внимание на Роберта Планта, бирмингемского вокалиста, известного по участию в группах Band of Joy и Obs-Tweedle. Побывав на концерте последних в Уолсолле, Грант и Пейдж немедленно направили певцу приглашение присоединиться к новому составу и получили от него согласие. Гитариста особенно потрясло на этом концерте исполнение Плантом «Somebody to Love», песни Jefferson Airplane. «От этих первобытных завываний мне стало жутковато. Это был тот самый голос, который я искал. Он пел уже несколько лет и при этом оставался практически неизвестен. Как такое могло случиться, до сих пор понять не могу», — вспоминал он.

Пейдж пригласил Планта на борт собственного небольшого катера, и на просторах Темзы музыканты рассказали друг другу каждый о своих пристрастиях. Выяснилось, что Плант глубоко знает американский кантри-блюз (его любимыми исполнителями были Скип Джеймс, Букка Уайт, Мемфис Минни) и мифологию «Властелина колец» (отсюда и Obs-Tweedle — название группы). На Пейджа это произвело впечатление. Он сыграл на гитаре «Babe I’m Gonna Leave You», песню из репертуара Джоан Баэз, и рассказал, что хотел бы в этой вещи выявить светлые и тёмные стороны — предельно контрастно, в совершенно новом контексте.

Мы словно бы пользовались одной колодой карт. Сразу ведь чувствуется, когда перед тобой человек, самые заветные двери приоткрывший чуть шире остальных. Таким человеком был Джимми. Как он впитывал в себя идеи, как при этом держался, — всё это было несравненно выше всего, с чем мне до тех пор доводилось сталкиваться. На меня он произвел сильнейшее впечатление.

— Роберт Плант, интервью Rolling Stone, 2006

После этого дома у Пейджа они в течение некоторого времени изучали музыкальные пристрастия друг друга, прослушивая любимые записи (Бадди Гай, The Incredible String Band, Мадди Уотерс).

В числе кандидатов на оставшееся вакантное место Пейджем рассматривались сессионные музыканты Клем Каттини (Clem Cattini) и Эйнсли Данбар (Aynsley Dunbar), Би Джей Уилсон из Procol Harum, Джинджер Бэйкер из Cream, а также некто Пол Фрэнсис (англ. Paul Francis). По рекомендации Роберта Планта в список кандидатов был включён ударник из Реддича Джон Бонэм. В июле 1968 года Пейдж и Грант, под впечатлением выступления Бонэма в составе группы Тима Роуза на концерте в Хэмпстеде, предложили тому войти в состав новой группы. Ударник, считая The Yardbirds «группой из прошлого, не имеющей будущего», поначалу отреагировал скептически; кроме того, у него уже имелись заманчивые предложения от Джо Кокера и Криса Фарлоу. Планту пришлось отправить 8 телеграмм в уолсоллский паб «Three Men in a Boat», где Бонэм был завсегдатаем; 40 телеграмм туда же отправил и Грант. В конечном итоге барабанщик принял предложение, решив, что музыка новой группы намного интереснее всего, что исполняли в то время Кокер и Фарлоу.

Свою первую репетицию квартет провел в небольшой комнатке квартиры, располагавшейся под музыкальным магазином на Джерард-стрит в Сохо. Пейдж предложил для начала сыграть «Train Kept A-Rollin'», рокабилли-трек из репертуара Yardbirds, популяризированный Джонни Бёрнеттом. «Едва только заиграл Джон Бонэм, как мы поняли: грядёт нечто выдающееся. С ним мы немедленно сомкнулись в единое целое», — вспоминал Джон Пол Джонс. Журнал Kerrang! так описывал эту первую репетицию группы:

…И вот четверо стоят лицом к лицу: волнением и предчувствиями пропитан воздух. 24-летний гитарист Джимми Пейдж и 22-летний бас-гитарист Джон Пол Джонс — уже опытные сессионные музыканты… Но оба впервые оказываются в одной репетиционной комнате с 19-летними Робертом Плантом и Джоном Бонэмом. Комнатка совсем маленькая: ме́ста в ней ровно столько, <сколько требуется>, чтобы вместить их четверых со своим оборудованием, и совсем уж крошечная, чтобы можно было скрыть некомпетентность, если она вдруг проявится. Выдав рифф, просто чтобы удостовериться в том, что звук из его динамика идёт «оглушающий», Пейдж бросает взгляд на Джонса и предлагает для начала пройтись по рок-н-ролльной классике: «Train Kept A Rollin’». Басист не очень-то с ней знаком, но — следует краткая инструкция, и старт взят. Бонэм за своей установкой — настоящий монстр; играет с мощью и самозабвением, каковых ни Пейдж, ни Джонс прежде не видывали. Вокалист — есть на что посмотреть: высокий, стройный, вьющаяся грива сотрясается в такт бою Бонэма; пронзительный вокал, подобный завыванию банши, разносится над всеобщим грохотом. Сочетание четырёх элементов столь мощное, что, закончив песню все четверо замирают и… разражаются смехом. Отчасти — от облегчения, отчасти — потому что понимают: только что с ними произошло что-то очень важное. Позже Пейдж не сможет вспомнить, какие ещё песни они вместе играли в тот вечер, — настолько потряс его тот изначальный звуковой штурм. И не раз ещё эти четверо музыкантов произведут тот же эффект.

— Kerrang! # 1244, 2009. Род Йейтс