結成3年目で『M-1』に出場。2001年大会は、初回ということもあって独特の緊張感に包まれていた。それまで、関西では人気を博していたフットだが、いざ漫才をすると、ダウンタウン・松本人志が55点、島田紳助さんが66点と低かった。「今は何となく85点(目安)になっていますけど、当時、50、60点は当たり前だった」と岩尾。2人以外の審査員は80、90点台だったものの、後藤は「僕は、“辞めよう”というところまでいきました。だって、憧れの人に“なし”って言われたわけですから」と振り返る。
「第2回大会に向けて、ネタの作り方を変更したフット。ショートネタを詰め込む形でしたが、漫才コントなど設定を一つに変えたそうです。それからというものの、関西の賞レースを総なめする形に。2002年の『M-1』では、松本からも紳助さんからも一転して褒められたとのこと。2人は翌年『M-1』を優勝するのですが、そのことよりも、第2回大会で松本と紳助さんに褒められた時の方が『嬉しかった』と口を揃えていましたね」(芸能ライター)
>>ハライチ岩井、2009年『M-1』のひと言でめちゃくちゃ怒られた?「テレビスタッフって終わってんだな」<<
当時、同大会に出場していたゲスト進行の笑い飯・西田幸治は、後藤について「(ほかの芸人がネタをしている最中)爪をガリガリ噛んで、目もイってしもてる」と言い、「(笑い飯のネタ終了後、裏に)戻ったら、後藤さんが殺したろかみたいな顔で見てきた」と明かした。当時について後藤は、笑い飯のネタは、会場が割れるほどの笑い声があり、あれほどの音が聞こえたのは、後にも先にも彼らの漫才だけだと述べた。
フットは、2006年『M-1』に再挑戦している。その理由について岩尾は、『M-1』優勝後に東京進出したものの、手応えを感じていなかったとコメント。後藤も、前年に優勝したブラックマヨネーズの完璧な漫才を見てショックを受け、出場を決意したと明かした。
2006年決勝は、後に優勝することとなるチュートリアルの空気に。ファイナルラウンドでは、居酒屋の設定で声を張り上げるネタだっため、普段そんなことを言わない後藤が「(テンションを)上げていけ」と岩尾に声を掛けた。後に大先輩のオール巨人から「岩尾くん、何を言っているのか分からへんかった」と言われたという。結果的に2位という好成績を残したが、「ボロ負けの2位」と分析していた。