「ブルース弾きの俺が呼ばれたってことは、ディランがチョーキングを多用したブルースを求めていると思ったんだ」ブルームフィールドは振り返る。「でもディランに言われたんだ。＂おいおい、誰がB.B.キングをやれって言った？＂ってね」。ディランの頭の中ではもう理想のサウンドが思い描かれていた。そして週明けの火曜日、ニューヨークにあるコロンビアのAスタジオに入った。本人曰く、ブルームフィールドは音楽ディレクターのような役割を果たしたという。プロデューサーのトム・ウィルソンは、アルバム『ブリンギング・イット・オール・バック・ホーム（原題：Bringing It All Back Home）』にも参加したポール・グリフィン（キーボード）、ボビー・グレッグ（ドラムス）、そして恐らくブルース・ラングホーン（ギター）などのスタジオミュージシャンに声をかけていた。彼らはまず『悲しみは果てしなく（原題：It Takes a Lot to Laugh, It Takes a Train To Cry）』の躍動感のあるバージョンを10テイク録り、その時は『ジェット・パイロット（原題：Phantom Engineer）』というタイトルをつけた。さらにロック色の強い『有刺鉄線の上で（原題：Sitting on a Barbed Wire Fence）』を6テイク録音した。
2015年に発表されたアルバムセット『ザ・カッティング・エッジ1965-1966：ザ・ブートレッグ・シリーズ第12集（原題：The Cutting Edge 1965 – 1966: The Bootleg Series Vol.12）』など各ブートレッグ・シリーズには各曲のさまざまなバージョンが収録されており、どのように『追憶のハイウェイ61』が作り上げられていったかを知ることができる。前作『ブリンギング・イット・オール・バック・ホーム（原題：Bringing It All Back Home）』ではディランのアコースティックギターがベースにあったが、『追憶のハイウェイ61』ではブルームフィールドのエレキギターがポイントで、ブルースをベースにカントリーやロカビリーまで広がりを見せた。次に彼らは『ライク・ア・ローリング・ストーン（原題：Like a Rolling Stone）』を5テイク録ったが、なかなか曲が固まらなかった。4テイク目を録り終えたところでディランが「もう声が出ないよ」と音を上げた。
レコーディング2日目、21歳のアル・クーパーがセッションに飛び入り参加した。クーパーはギタリストだが、スタジオではオルガンの前に座り（彼いわく＂暗闇で子供が電気のスイッチを手探りするように＂）、曲に合わせて弾いた。「このレコーディングでは素人同然で、いい教訓になったよ」と、クーパーは最近白状している。
クーパーがオルガン、グリフィンがピアノを担当し、『ライク・ア・ローリング・ストーン』を2回リハーサルした後、4つのテイクを録音しながら曲を完成させていった。その時点でもうあの歴史的な曲は完成していたのだが（当時の彼らには知る由もないが）、彼らは試行錯誤しながらさらに11テイク録音した。
シングルは1965年7月20日にリリースされた。ラジオ局向けの初回盤は、6分間の曲をシングル盤のA面とB面に分けて収録した。しかしファンたちは「1曲を通しで聴きたい」と主張し、それが実現した。「時が永遠に続くように思えた。とにかく美しい曲だった。ディランは俺たちみんなに＂誰もがもう少し前向きに生きられるんだ＂ということを教えてくれた」とポール・マッカートニーは、ジョン・レノンの家でこの曲を初めて聴いた時の印象を語っている。
