次なる修行食材、メロウコーラを手に入れる為、大砂漠・サンドガーデンへとやってきたトリコと小松、そしてゼブラ。当初、小松は死刑囚であるゼブラの同行に反対していたが、やがて彼が単なる犯罪者ではない事を知り、その考えを改めるのだった。ゼブラに謝る小松。ゼブラは呼吸・脈拍等から、その謝罪が本心からだと見抜く。ゼブラは「チョーシにのっている」奴が大嫌いだ。そして最も「チョーシにのっている」行為は、嘘をつく事だと考えていた。表で仲良くしつつ、陰では悪口…そんな態度が最高にムカつくのだ。本心から「チョーシにのってました」と謝る小松をゼブラは笑い飛ばし、条件付きで許してやると凄むのであった。

町でラクダを借りて、トリコたちは砂漠を進んでいく。やがて、迫り来る猛獣の気配を察するゼブラ。砂を泳ぐサメ・砂漠鮫（デザートシャーク）だ。襲いかかってきた砂漠鮫の群れを、ゼブラは人には聞こえない周波数の声、超音波で追い払うのだった。そうして旅を続け、やがて一行は真っ赤な砂漠・デザートラビリンスへと到着した。いよいよここからが本番だ。日中の気温が60度を超えるサンドガーデンの中でもココは別格、一歩足を踏み入れただけで、今までとは桁違いの暑さがトリコたちを襲う。グルメ界でも味わった灼熱地獄に近い熱気にトリコは戦慄し、水分を補給するよう小松へ忠告する。だが振り返った時、既に小松の姿はなくなっていた…！

うろたえるトリコらの周りに、直後、蜃気楼と巨大な流砂が発生した。どうやら小松はこれらに連れ去られてしまったようだ。トリコは小松を捜すようゼブラに頼む。だが、そこへ様々な猛獣の大群が襲いかかってきた。猛獣の相手をトリコに任せ、声を張り上げるゼブラ。必殺技・エコーロケーションである。超音波の反響で、まるでレーダーさながらに、視覚に惑わされない正確な地形を把握する技だ。そうしてゼブラは無事に小松を発見。どうやら流砂によって何処かへ流されてしまっているようだった。今の所はまだ無事なようだが、急がなければ。猛獣たちを一蹴して、トリコたちは小松を追いかけるのであった。

ゼブラが展開するレーダーマップを頼りに、トリコらは慎重に、しかし急いで先を行く。その中で、徐々にデザートラビリンスの熱気に適応していくトリコ。ゼブラもまた、刑務所のマグマシーズンで暑さに耐性を得ていた。猛暑の中を急ぎながらトリコは、小松がはぐれたのは運が良かったのかも知れないと考えていた。小松では、この灼熱地獄に耐えるのは難しかっただろうからだ。トリコの呟きにゼブラも頷く。小松の運は本物かもしれない、と。というのも、小松を追いかけて辿り着いた先は、なんとトリコたちの目的地…、世界グルメ七不思議のひとつ・グルメピラミッドだったのだ！