68年の7月、パーソンズはアパルトヘイト体制下の南アフリカで演奏することを拒んだことが原因で、バーズから解雇される。ただ、バーズのバンドメイトの中には、パーソンズが南アフリカに行かなかったのは、アパルトヘイトに対する政治的な主張が原因というよりも、新しく友人になったキース・リチャーズが、フランスでストーンズの『Exile on Main St.』のレコーディングをしているので遊びに行きたかっただけではないかと思っていた者もいたようだ。リチャーズは、カントリー・ミュージックの詩的な部分やソウルを情熱的に語り、カントリー・ジャンルへの造詣も深いパーソンズに非常に興味を持っていたという。
音楽史家の中にはパーソンズこそがストーンズにカントリー・ミュージックを紹介したという者もあるが、ストーンズはパーソンズとの出会い以前にハンク・スノウの“I’m Moving On”をカヴァーしているし、アルバム『Beggars Banquet』（68年）には明らかにカントリーの影響がある。実際には、パーソンズとの出会いがストーンズのカントリー・ミュージックに対する興味を再燃させ、さらに深めたというのがより正確なところではないだろうか。最終的には、パーソンズはフランスの屋敷からも出ていくよう要請される。彼のことを不快に思ったり、すでにヘロインにハマっていたキース・リチャーズへ悪い影響を及ぼしていると思ったりする者がいたようだ。
LAに戻ったパーソンズはすぐに新しいバンドを結成する。以前インターナショナル・サブマリン・バンドで一緒だったクリス・エスリッジ（ベース、ピアノ）をリクルートし、バンド名をフライング・ブリトー・ブラザーズとした。バーズからパーソンズをクビにしたヒルマンも新バンドに参加。ヒルマンは当初バーズでは触ったこともないベースを担当するが、後に、昔フォークやブルーグラスのバンドにいた際に弾いていたギターやマンドリンに移行する。また、スチール・ペダル奏者のスニーキー・ピートがバンドを完成させる。ドラマーには次々と候補が現れ、バンドのデビュー・アルバム『Gilded Palace of Sin』（69年）では四人のドラマーがクレジットに名を連ねている。このアルバムは非常に評価が高く、ボブ・ディランもこのアルバムに高評価をつけた。しかし、売り上げはパッとせず、ビルボードチャートも164位とあまり振るわなかった。しかし、今日このアルバムは人気も高く、パーソンズのベスト盤と評する人も多い。
パーソンズは“Hot Burrito #1”や“Hot Burrito #2”など、収録されている11曲中9曲をヒルマンと共に作曲（このアルバムの熱烈なファンだったエルヴィス・コステロは、後に“Hot Burrito #1”を“I'm Your Toy”と改題してカヴァーしている）。この2曲は素晴らしく心を打つラヴソングで、メキシコ料理のブリトーには全く関係がない。多くのファンは、“Hot Burrito #1”でのパーソンズのヴォーカルが彼のベストワークと言うだろう。
このアルバムには、他にもダン・ペンとチップ・モマンという、R&Bやカントリーのシンガーによくカヴァーされることで有名な二人が作曲した2曲も含まれている。“Do Right Woman”はアレサ・フランクリンのヒット曲だし、“Dark End of the Street”はジェイムズ・カーのヒット曲。ブリトーズは、後にスタンダード・ナンバーに数えられるこれらの曲に、カントリー・ミュージックのソウルを持ち込んだと言えるだろう。
成功に手が届かないことで傷つきながらもフライング・ブリトー・ブラザーズは活動を続けるが、エスリッジが脱退したため、ギタリストのバーニー・レドンが加入する。レドンは数年後に大人気カントリー・ロック・バンドとなるイーグルスの創立メンバーで、その後も〈鳥名バンド〉を続けていく。他にも、バーズの前のドラマー、マイケル・クラークが正式に加入。しかし、セカンド・アルバム『Burrito Deluxe』は新曲ができず難産だったという。パーソンズは11曲中5曲をヒルマンと合作し、インターナショナル・サブマリン・バンド時代の曲“Lazy Days”も採用した。
『Burrito Deluxe』に収録されたうちの4曲はカヴァーで、その中でも、ストーンズのキース・リチャーズとミック・ジャガーが作曲した未発表曲“Wild Hourses”は注目すべき楽曲だ。リチャーズは69年12月、2人のバンドが参加した〈アルタモント・フェスティバル〉の直後、パーソンズにこの曲のデモを渡したという。パーソンズがこの曲の作曲に関わったという者もいるが、真偽は定かではない（この頃、ストーンズのギタリストだったミック・テイラーも多く作曲していたが、クレジットに名前が載ることはなかった）。とはいえ“Wild Horses”はヒットとはならず、アルバムがビルボードのトップ200に引っかかることもなかった。
ちょうどこの頃、パーソンズはギグをすっぽかしたり、演奏できないほどベロベロになって現れたりするなど、飲酒と薬物の両方の問題を抱えていた。また、バンド・メンバーは生きていくのにギリギリの生活をしていたにも関わらず、パーソンズは両親からの遺産があったため金に困っていなかった。大して収入にならないライブにリムジンで乗りつけてバンド・メンバーの反感を買うなど、様々な行動をした結果、ついにパーソンズは自身がリーダーを勤めていたフライング・ブリトー・ブラザーズからも解雇されてしまう。パーソンズの代役として起用されたのは、リック・ロジャーズという誰も知らないミュージシャンだった。彼はブリトーでは成功しなかったが、のちにファイアフォールというバンドのリーダーとして成功を治めた。
