時は紀元前400年1月。サルディスを出発したのは前年401年3月のことである。クセノフォンらギリシア人傭兵部隊「万人隊（ミュリオイ）」は、すでに9か月に及ぶ行軍と戦闘を重ね、故郷イオニアの温かい海岸から数千キロも離れた地を進んでいた。それでも彼らは、カリュブ人やタオコイ人の国を抜け、黒海の岸へたどり着かなければならなかった。
タオコイ人の峠――石つぶてとの知恵比べ
タオコイ人の国は山がちで険しい土地だった。ここでもギリシア軍は狭い峠道を通らねばならなかった。しかし敵はすでに山頂を押さえており、幅わずか15メートルほどの細い山道を通ろうとする者に向かって、巨大な岩を次々と転がし落としてきた。
そこでギリシア人は一計を案じた。峠のすぐそばに広がる松林に兵士たちを送り込み、そこから抜け出そうとするふりをさせたのである。敵は夢中になって石を投げ続けたが、ギリシア兵はそのたびに松林へ引き返し、大きな松の幹の陰に身を隠した。やがて敵側の「弾薬」が尽きると、ギリシア軍は一気に突撃して敵の陣地を占領した。
しかしタオコイ人には捕虜になるつもりなどさらになかった。男も女も子どもまでもが一斉に断崖から身を投げ、自ら命を絶ったのである。敵を押さえようとして、もみ合ったまま崖下へ転落したアイネイアス・スティムファリオスもここで命を落とした。結局、生け捕りにできたタオコイ人はごくわずかだった。一方、ギリシア軍の手には牛・羊・若い雌牛が大量に渡ることとなった。
カリュブ人の国を抜けてスキタイ人の国へ
勝利を収めたギリシア軍は、続いてカリュブ人の国を行軍した。この人々は要塞化された都市に住み、略奪による食料調達を一切許さなかった。幸い、タオコイ人から奪った家畜があったため、軍の食料には困らなかったという。こうしてギリシア軍はアルパス川（現在のアルパ・チャイ）を渡り、今日のトルコとジョージアの国境付近にあたるスキタイ人の国へ入った。
「タラッタ！タラッタ！」――ついに海を見た
スキタイ人はギリシア人に友好的で、食料と案内人を提供してくれた。そしてギュムニアス（おそらく現在のエルズルム）の執政官は、「5日間行軉すれば海の見える場所へ必ず案内する。できなければ自分の首を差し出す」と誓う案内人を派遣した。案内人は見事に約束を守った。
彼はギリシア軍を、スキタイ人に敵対する部族の土地へ導き、「焼き払え、奪え」と告げた。スキタイ人が進んで協力したのは、宿敵を懲らしめるためにギリシア軍を「利用」する意図があったからである。そして行軍5日目、先頭部隊の兵士たちがテュケース山（シケリアのディオドロスによればケニオン山）の頂上から、ついに海を目にしたのだ。兵士たちは涙を流し、互いに抱き合いながら、あの有名な叫び声を上げた――「タラッタ！タラッタ！」（海だ！海だ！）
後衛の兵たちは何が起きたのか分からず、敵の伏撃を恐れて慌てて山を駆け上がった。当時、スキタイ人の敵対部族はすでにギリシアの密集隊形を悩ませており、小規模な衝突も発生していたからだ。しかし頂上に立って海を望んだ後衛の兵たちは、将軍たちや隊長たちと抱き合って喜びを分かち合った。そして一行は、これまでの行軍と戦いと勝利を記念する石塚を築くことを決めた。
案内人には手厚い報酬が与えられた。金貨10枚、立派な馬1頭、衣服、銀製の水差し、そして数多くの指輪である。帰国する前に彼は、一行が休息できる町を教え、トラペズスの南方に位置するマクロネス人の国へ至る道についての情報まで残していった。
マクロネス人の国で――通訳になった解放奴隷
さらに55キロを行軍すると、ギリシア軍はマクロネス人の領内に踏み込んだ。ここでもまた険しい地形に苦しめられた。右手には山々が連なり、左手には名も知れぬ川が流れている。正面には林が広がり、木は大きくないものの鬱蒼と茂っていたため、ギリシア兵はやむなく斧を振るって道を切り開いていった。
ところが林の出口には、マクロネス人が整然と隊列を組んで待ち構えていた。一部の敵兵は遠くから石を投げてきたが、距離がありすぎてギリシア軍には届かなかった。
そのとき、マクロネス語を解するという一人の兵士――元奴隷の解放奴隷――がクセノフォンの前に現れた。クセノフォンはただちにその兵を連れてマクロネス人のところへ赴き、なぜ攻撃しようとするのかを問うた。マクロネス人の答えは、「ギリシア人が侵入してきた我が国を守るためだ」というものだった。
クセノフォンはこの通訳を介してこう説いた。ギリシア人が望むのは、ただ自国の領土を通過することだけだ。悪意はない。われわれはアルタクセルクセス王と戦い、今はただ故郷へ帰ろうとしているのだ、と。この説明によって、マクロネス人とギリシア人は協定を結んだ。協定に基づき、マクロネス人はギリシア軍のために森の中の道を開削する手助けをし、食料の売買にも応じた。3日後に作業は完了し、ギリシア軍はコルキス人の国へ向けて進軍した。
コルキス人との決戦――クセノフォンの布陣術
マクロネス人の国との国境では、コルキス人が早くも大山地の斜面に展開し、峠を上から押さえて待ち構えていた。これを見たギリシア軍は直ちに戦闘隊形を整えた。クセノフォンの提案により、重装歩兵の中隊は縦深を厚く取る一方、中隊間に空白を設けるという独特の陣形が採られた。
この布陣の狙いはこうだ。両翼の部隊は敵の戦列を迂回して包囲できる。中央の部隊は縦深のおかげで十分な凝集力を保ち、いかなる攻撃にも耐えられる。仮に敵が中隊間の隙間に飛び込めば、少なくとも二つの中隊から同時に攻撃を受けて壊滅するため、誰もそこへ入ろうとはしない、という計算である。さらに軽装部隊は各600人ずつの三個部隊に分割され、左翼端・中央・右翼端に配置された。こうしてファランクスの中央部は守られ、両翼は敵の包囲から防護されると同時に、こちらから敵の翼を脅かす矛先ともなった。
クセノフォンによれば、このとき展開していたギリシア軍の総兵力は戦闘員9,800人。出発から約10か月での損害は約3,000人ということになり、1日あたりの死傷率は10人前後。その偉業の規模を考えれば、比較的低い数字といえるだろう。
祈りを捧げ、パイアーン（凱歌）を歌い終えると、ギリシア軍は敵へ向かって前進した。両翼から包囲される危険を察したコルキス人は戦列を横に広げようとしたが、その機動が拙すぎたため、戦列中央に大きな空洞が生じてしまった。
もちろんギリシア軍はこの好機を見逃さなかった。アカルナニア出身のアイスキネスが率いる中央の軽装歩兵部隊がその隙間へ殺到し、敵の戦線全体を粉砕した。重装歩兵の中隊が続々と到着するに及んで、コルキス人は持ちこたえられず、統制を失って潰走したのである。
無秩序な蛮族の寄せ集めが、世界で最も完璧な軍事機械であるギリシアのプロフェッショナル軍団に対抗できるはずがなかったのである。
有毒なハチミツとトラペズスへの到達
新たな勝利の後、ギリシア軍はコルキス人の領内へ進み、村々が点在し食料に富んだ地域に達した。しかしそこには「非常に強烈なハチミツ」もあった。これを口にした兵士たちは相次いで体調を崩したという（これは当地に自生するツツジ属の花蜜に含まれる毒によるもので、後にストラボンも言及している）。こうしてさらに40キロを進んだ末、ギリシア軍はついにトラペズス（現在のトルコ・トラブゾン）に到着した。同市はシノーペー人が建設したギリシア植民都市であり、シノーペー人自身はミレトス人からの移民の子孫であった。