「熱狂的な1週間を過ごした後、オックスフォードからヒッチハイクで戻った僕はジョン（ボーナム）を捕まえて言った。“兄弟、お前はヤードバーズに入るべきだ”」とプラントは、『トランプルド・アンダーフット』で振り返る。「その時の僕には、アメリカン・ポップの歴史に埋もれたバンド名以外に、彼を説得する材料が何もなかった」
ドラマーのジョン・ボーナムはプラントの生涯の友人で、過去にも何度か一緒にバンドを組んでいた。ボーナムもまた、ロンドン・シーンで埋もれていた才能のひとりだった。しかしペイジは彼のプレイを聴いた瞬間に、その壮大なプレイスタイルの虜になった。唯一のネックは、ボーナムはその時シンガーのティム・ローズのバックを努めており、それなりの収入があったということだった。ボーナムの妻パットは、夫がプラントと全く売れるかどうかもわからない新たな冒険に出ることに乗り気でなかった。ついにグラントとペイジは、彼に対する報酬額を引き上げることでボーナムを説き伏せた。
パズルの最後のピースは、彼らにマッチするベース・プレイヤーを探すことだった。ペイジにとって幸運なことに、世界トップレベルのプレイヤーが彼のもとに舞い込んできた。「メロディメイカー誌に掲載されていた求人広告に応募したんだ」と、ジョン・ポール・ジョーンズは1975年に行ったキャメロン・クロウとのインタヴューで語っている。「妻が後押ししてくれたんだ」という。彼自身はメロディメイカー誌の広告を真剣に受け止めていなかったが、ジョン・ポール・ジョーンズがペイジのやろうとしていることを感じ取ったのは事実で、妻の勧めもあって応募した。ギタリストとしてセッション・プレイヤー時代にジョーンズと一緒に仕事をして彼のことを知っていたペイジは、考える間もなくジョーンズからの参加表明を受け入れた。すぐさま彼は、スタジオでの彼のプレイを支え、信頼できるプレイヤーに出会ったと確信した。その後の年月が示す通り、ジョーンズはロックの歴史上最もダイナミックなマルチ・インストゥルメンタル・ユーティリティ・プレイヤー＆アレンジャーとして、ペイジの壮大な音楽的アイディアの実現をサポートすることとなる。
その後レッド・ツェッペリンを結成することとなる4人の男たちは、1968年8月12日、ロンドンのジェラード・ストリートにある狭い地下室に初めて集合した。彼らはすぐさま、自分たちには何か特別なことが起きることを悟った。「僕らは狭いリハーサル室に集まり、ヤードバーズ時代の曲でロバートも知っているであろう『トレイン・ケプト・ア・ローリン』をプレイした」とペイジは、1990年に語っている。「曲をプレイし終えた僕らは、本当に電気が走ったような感じで、正にエキサイティングだった。そこからアルバムへ向けたリハーサルが始まった」
スカンジナビアでの2週間のツアーへ向けたリハーサルを続けている彼らに、興味深いチャンスが訪れた。テキサス生まれのポップ・シンガー、P・J・プロビーが、ニュー・アルバムのセッションにジョン・ポール・ジョーンズを数週間前から指名していた。ジョーンズはその仕事をキャンセルせず、新しい彼のバンド仲間をプロビーのレコーディングに呼ぶことにしたのだ。ペイジは特に、このエキセントリックなシンガーのレコーディングのサポートに乗り気だった。彼は1964年、プロビーの全英第3位のヒット曲『ホールド・ミー』のレコーディングに参加していた。レッド・ツェッペリンの初飛行は、自身のデビュー・アルバムではなく、プロビーの1969年のアルバム『スリー・ウィーク・ヒーロー』ということになる。
