Vào thời điểm này, Pharnabazus vì lo sợ quân đội có thể thực hiện một chiến dịch tấn công vào lãnh địa của mình, đã cho người đến gặp Anaxibius, vị đô đốc cấp cao của người Spartan đang tình cờ có mặt tại Byzantium, khẩn khoản yêu cầu ông đưa quân đội rời khỏi châu Á, đồng thời hứa hẹn sẽ đáp ứng mọi yêu cầu của ông. Theo đó, Anaxibius triệu tập các tướng lĩnh và sĩ quan đến Byzantium, hứa rằng binh lính sẽ không thiếu lương nếu họ chịu vượt qua eo biển. Các sĩ quan nói họ sẽ bàn bạc và trả lời sau. Xenophon riêng lẻ báo cho họ biết ông định rời quân đội ngay lập tức, và chỉ mong được sớm lên thuyền ra đi. Anaxibius thúc giục ông đừng quá vội vàng: "Hãy qua sông cùng với những người khác," ông nói, "rồi lúc đó nghĩ đến chuyện rời quân đội cũng chưa muộn." Xenophon đồng ý làm theo lời ông.

Trong khi đó, Seuthes người Thracia sai Medosades tới khẩn khoản Xenophon dùng ảnh hưởng của mình để giúp quân đội qua sông. "Hãy nói với Xenophon rằng, nếu ông ấy tận tâm giúp tôi việc này, ông ấy sẽ không phải hối tiếc." Xenophon đáp: "Đằng nào thì quân đội cũng sẽ qua sông; cho nên, về việc đó, Seuthes không nợ tôi hay bất cứ ai cả; nhưng ngay khi quân đội qua sông, cá nhân tôi sẽ rút lui. Vậy nên, Seuthes cứ tùy nghi liệu xét, hãy tìm đến những người sẽ ở lại và có quyền quyết định mọi việc."

Sau đó, toàn bộ quân đội vượt sang Byzantium. Nhưng Anaxibius, thay vì trả lương, lại tuyên bố rằng: "Binh lính hãy mang theo vũ khí và hành lý rồi rời khỏi đây," cứ như thể điều ông ta muốn chỉ là kiểm kê số lượng rồi tiễn biệt họ cùng một lúc. Binh lính không mấy hài lòng về điều đó, vì họ chẳng có tiền để mua lương thực cho cuộc hành quân; và họ uể oải bắt đầu thu dọn hành lý. Trong khi đó, Xenophon, vốn thân thiết với viên thống đốc Cleander, bèn đến chào tạm biệt vị chủ nhà lần cuối, vì ông sắp sửa lên thuyền ra đi. Nhưng Cleander can ngăn: "Đừng làm thế, nếu không," ông nói, "ông sẽ bị khiển trách đấy, vì hiện nay đã có một số kẻ chực chờ đổ lỗi cho ông vì quân đội chậm trễ xuất phát." Xenophon đáp: "Không, tôi không có lỗi trong việc đó. Chính bản thân binh lính đang thiếu lương thực; đó là lý do tại sao họ chán nản trước cuộc di cư này." "Dù sao đi nữa," ông ta trả lời, "tôi khuyên ông nên ra ngoài, như thể ông định hành quân cùng họ, và khi đã ra ngoài hẳn rồi thì lúc đó muốn rời đi cũng chưa muộn." "Được rồi," Xenophon nói, "chúng ta sẽ đi và sắp xếp mọi chuyện với Anaxibius." Họ đi và trình bày sự việc với vị đô đốc, người khăng khăng rằng họ phải làm đúng như ông ta đã nói, và hành quân ra ngoài, mang theo cả hành lý, bằng con đường nhanh nhất; và như một phụ lục cho sắc lệnh trước đó, ông ta thêm vào: "Kẻ nào vắng mặt trong buổi duyệt binh và tập hợp sẽ tự gánh lấy hậu quả." Lệnh ban ra vô cùng nghiêm ngặt. Thế là quân đội hành quân ra ngoài, các tướng lĩnh đi trước, binh lính theo sau; và rồi, ngoại trừ lác đác vài người, tất cả đều đã ra ngoài; đó là một cuộc "quét sạch" triệt để; và Eteonicus đứng gần cổng, sẵn sàng đóng cửa ngay khi quân lính vừa ra hết và cài chốt lại.

Sau đó Anaxibius triệu tập các tướng lĩnh và đội trưởng, rồi tuyên bố: "Các anh tốt nhất nên lấy lương thực từ các ngôi làng Thracia; ở đó các anh sẽ tìm thấy rất nhiều lúa mạch, lúa mì và những nhu yếu phẩm khác; và khi đã có đủ, hãy lập tức tiến về Chersonese, nơi Cyniscus sẽ nhận các anh vào phục vụ." Một vài binh lính tình cờ nghe được những lời đó, hoặc có lẽ một trong các sĩ quan là người truyền tin; dù thế nào đi nữa, tin tức cũng đã truyền đến tai toàn quân. Về phần các tướng lĩnh, mối quan tâm trước mắt của họ là cố gắng tìm hiểu thông tin về Seuthes: "Ông ta là thù hay bạn? Họ sẽ phải hành quân qua ngọn núi Sacred (1), hay đi vòng qua trung tâm Thracia?"

Trong khi họ đang bàn luận những điểm này, binh lính chộp lấy vũ khí và lao nhanh với tốc độ tối đa về phía cổng, quyết tâm quay ngược vào trong thành. Nhưng Eteonicus và quân của ông ta, thấy bộ binh nặng lao tới, liền lập tức đóng cổng và cài chốt. Sau đó binh lính bắt đầu đập phá cổng, gào thét rằng việc đẩy họ ra ngoài nanh vuốt kẻ thù như thế này thật là bất công. "Nếu các người không tự mở cổng," họ hô lớn, "chúng ta sẽ đập nát nó ra!"; và một toán khác chạy xuống phía biển, men theo đê chắn sóng rồi vượt tường vào thành; trong khi toán thứ ba, gồm những người vẫn còn ở trong thành chưa kịp rời đi, thấy cảnh tượng ở cổng bèn dùng rìu chặt đứt then cài, mở toang cửa chính; và những người còn lại ùa vào.

Chứng kiến cảnh tượng này, Xenophon vô cùng lo sợ quân đội sẽ cướp bóc, gây ra tai họa không thể cứu vãn cho thành phố, cho chính bản thân ông và cho cả binh lính. Ông lập tức lao vào đám đông và bị cuốn qua cổng cùng với họ. Người dân Byzantium vừa thấy binh lính xông vào liền bỏ quảng trường, kẻ chạy ra bến tàu, người chạy về nhà, còn những ai đang ở trong nhà cũng hớt hải chạy ra. Một số người bắt đầu kéo các tàu chiến xuống nước, hy vọng có thể an toàn trên tàu; không một ai còn nghi ngờ gì việc thành phố đã bị chiếm và tất cả đều tiêu đời. Eteonicus vội vã rút lui vào thành nội. Anaxibius chạy xuống bờ biển, nhảy lên một chiếc thuyền đánh cá, dong buồm đến pháo đài, và lập tức phái người đi triệu tập quân đồn trú từ Chalcedon, vì số quân hiện có trong pháo đài xem chừng không đủ để kiềm chế binh lính.

Binh lính nhìn thấy Xenophon liền ùa tới, kêu lên: "Xenophon, giờ là lúc ông chứng tỏ bản lĩnh của mình. Ông có thành phố trong tay, có chiến thuyền, có tiền bạc, có quân lính; hôm nay, chỉ cần ông muốn, ông có thể giúp chúng tôi một việc lớn, và chúng tôi sẽ tôn ông lên hàng đại nhân." Ông đáp: "Không, ta rất thích ý định của các anh, và ta sẽ làm tất cả; nhưng nếu đó là điều các anh hằng mong mỏi, hãy vào hàng ngũ và đứng vào vị trí ngay đi." Ông nói vậy cốt để trấn an họ, rồi chính ông truyền lệnh dọc theo các hàng quân, đồng thời bảo những người khác cũng làm như vậy: "Vào vị trí; nghỉ." Bản thân binh lính, nhờ một kiểu tự dàn trận, đã nhanh chóng vào hàng ngũ, hình thành đội hình bộ binh nặng tám hàng, trong khi bộ binh nhẹ chạy lên yểm trợ cả hai cánh. Quảng trường Thracia, như người ta vẫn gọi, là một địa điểm tuyệt vời để tập trận vì bằng phẳng và không có công trình xây dựng. Khi vũ khí đã được xếp chồng lên và cơn giận của binh lính đã dịu xuống, Xenophon triệu tập một cuộc họp chung của binh lính và đọc diễn văn:

"Hỡi các binh sĩ, ta không ngạc nhiên trước cơn giận của các anh, cũng không ngạc nhiên khi các anh coi việc bị lừa dối như thế này là một sự sỉ nhục; nhưng hãy cân nhắc xem hậu quả sẽ ra sao nếu chúng ta thỏa mãn cơn thịnh nộ này, và để trả đũa sự lừa lọc ấy, chúng ta lại quay sang báo thù người Lacedaemonia đang ở đây và cướp bóc một thành phố vô tội. Chúng ta sẽ bị tuyên bố là kẻ thù của người Lacedaemonia và đồng minh của họ; và chúng ta chẳng cần phải đi đâu xa để biết đó sẽ là một cuộc chiến như thế nào. Chắc các anh vẫn chưa quên những sự kiện vừa mới xảy ra gần đây. Chúng ta, những người Athen, từng tham chiến chống lại người Lacedaemonia và đồng minh của họ với một hạm đội gồm không dưới ba trăm chiến thuyền, cả những chiếc ở ụ tàu lẫn những chiếc đang ngoài khơi. Chúng ta từng có kho báu khổng lồ tích trữ trong thành, cùng nguồn thu nhập hàng năm từ trong nước và nước ngoài lên đến không dưới một ngàn talent. Đế chế của chúng ta bao trùm tất cả các hòn đảo, và chúng ta sở hữu vô số thành phố cả ở châu Á lẫn châu Âu. Trong số đó, chính cái thành Byzantium nơi chúng ta đang đứng đây cũng từng là của chúng ta; vậy mà cuối cùng chúng ta vẫn bị đánh bại, như tất cả các anh đều biết rõ."

"Giờ đây, chúng ta phải lường trước điều gì sẽ xảy đến với mình? Người Lacedaemonia giờ không chỉ có đồng minh cũ, mà còn có cả người Athen và những kẻ từng là đồng minh của Athen gia nhập hàng ngũ. Tissaphernes cùng tất cả những người châu Á khác ở vùng duyên hải đều là kẻ thù của chúng ta, chưa kể tới kẻ thù không đội trời chung là chính đức vua ở trên kia, người mà chúng ta đã đến đây để tước đoạt đế chế, thậm chí là lấy mạng nếu có thể. Vậy ta hỏi các anh, khi tất cả những thế lực này hợp sức chống lại chúng ta, liệu có kẻ nào ngu muội đến mức tin rằng chúng ta có thể sống sót sau cuộc giao tranh này không? Vì trời đất chứng giám, xin đừng để chúng ta trở nên điên rồ hoặc vứt bỏ mạng sống một cách vô nghĩa trong cuộc chiến với chính những thành phố quê hương mình—không, với chính bạn bè, người thân, và đồng bào mình; bởi vì dù ở thành phố nào, họ cũng đều là người của chúng ta cả. Mọi thành phố sẽ hành quân chống lại chúng ta, và điều đó chẳng hề bất công, nếu sau khi từ chối chiếm lấy một thành phố man di bằng quyền chinh phạt, chúng ta lại quay sang cướp bóc và biến thành phố Hy Lạp đầu tiên mà mình gặp thành một đống đổ nát. Về phần mình, ta cầu nguyện rằng trước khi nhìn thấy các anh làm điều đó, ta thà nằm dưới mười ngàn sải đất còn hơn! Lời khuyên của ta dành cho các anh, với tư cách là những người Hy Lạp, là hãy cố gắng đạt được các quyền lợi chính đáng thông qua việc phục tùng những người đứng đầu Hy Lạp; và nếu các anh thất bại trong những đòi hỏi đó, thì tại sao, khi đã là người chịu nhiều thiệt thòi hơn là gây ra lỗi lầm, chúng ta lại phải tự tước bỏ cả chính Hy Lạp của mình? Hiện tại, ta đề nghị chúng ta nên gửi người đến gặp Anaxibius và thông báo rằng chúng ta vào thành phố không phải vì âm mưu bạo lực, mà chỉ để xem ông ta và những người của ông ta có thành tâm với chúng ta hay không; nếu họ thành tâm, thì tốt; nhưng nếu không, ít nhất chúng ta cũng cho họ thấy rằng chúng ta không để họ đóng cửa nhốt mình như những kẻ ngốc nghếch bị lừa. Chúng ta biết kỷ luật nghĩa là gì; chúng ta sẽ quay lưng rời đi."

Quyết định này được thông qua, và họ cử Hieronymus người Elea, cùng hai người nữa là Eurylochus người Arcadia và Philesius người Achaea, đi truyền đạt thông điệp. Họ lên đường thực hiện nhiệm vụ. Trong khi binh lính vẫn đang ngồi hội nghị, Coeratadas, người Thebes, xuất hiện. Ông ta không phải là một kẻ lưu vong, mà là một người có khiếu chỉ huy, luôn tìm kiếm xem liệu thành phố hay quốc gia nào cần đến sự phục vụ của mình. Nhân cơ hội này, ông ta tự tiến cử và bày tỏ sẵn sàng đứng ra lãnh đạo họ tiến vào vùng Delta của Thracia (2), nơi ông ta hứa hẹn họ sẽ tìm thấy một vùng đất trù phú; còn trước khi tới đó, ông ta sẽ cung cấp đầy đủ lương thực, nước uống cho họ. Trong khi họ còn đang lắng nghe câu chuyện đó thì thông điệp phản hồi từ Anaxibius tới. Câu trả lời của ông ta là: "Kỷ luật mà các anh nói đến là điều các anh sẽ không phải hối tiếc; quả thực ông ta sẽ báo cáo hành vi của các anh với chính quyền tại quê nhà; còn về phần mình, ông ta sẽ xem xét và làm những gì tốt nhất có thể cho các anh."

Sau đó, binh lính chấp nhận Coeratadas làm tướng lĩnh của mình và rút lui ra ngoài tường thành. Vị tướng mới hứa sẽ có mặt cùng quân đội vào ngày hôm sau với gia súc để tế lễ và một thầy bói, cùng với lương thực, nước uống cho toàn quân. Ngay khi họ vừa ra khỏi thành, Anaxibius đóng cổng lại và ban bố lệnh rằng: "Bất kỳ binh lính nào bị bắt gặp ở bên trong sẽ bị đem ra đấu giá và bán ngay lập tức." Ngày hôm sau, Coeratadas đến cùng với các con vật tế lễ và thầy bói. Theo sau ông ta là một hàng dài gồm hai mươi người khuân vác bột lúa mạch, tiếp theo là hai mươi người khác mang rượu, ba người chở đầy ô liu, và hai người nữa, một người vác gánh tỏi to như một người có thể nâng, và người kia vác một gánh hành tương tự. Ông ta đặt những nhu yếu phẩm này xuống, dường như để phân phát, rồi bắt đầu làm lễ tế.

Xenophon sai người đến gặp Cleander, khẩn khoản nhờ ông ta dàn xếp để cho phép ông vào thành, với ý định rời khỏi Byzantium để lên đường về nhà. Cleander đến và nói: "Ta đã đến; nhưng ta khó khăn lắm mới dàn xếp được điều ông muốn. Anaxibius cứ khăng khăng: 'Không tiện để Xenophon ở trong thành khi binh lính đang ở sát bên ngoài; hơn nữa, người Byzantium đang rối như canh hẹ; và các phe phái trong thành chẳng ưa gì nhau.' Dù vậy, cuối cùng ông ta cũng đồng ý cho ông vào trong, nếu ông thực sự muốn rời thành phố bằng đường biển cùng với chính ông ta." Theo đó, Xenophon chào từ biệt binh lính và cùng Cleander quay trở vào thành.

Quay lại với Coeratadas. Ngày đầu tiên, ông ta không nhận được điềm lành từ lễ tế, và chẳng hề phân phát được một khẩu phần lương thực nào cho binh lính. Đến ngày thứ hai, các con vật tế lễ đã đứng sẵn gần bàn thờ, và Coeratadas cũng đã sẵn sàng với vòng hoa trên đầu để hành lễ, thì Timasion người Dardania, cùng với Neon người Asinaea và Cleanor người Orchomenus, xông tới ngăn cản Coeratadas tế lễ: "Ông ta phải hiểu rằng chức chỉ huy của ông ta đã chấm dứt, trừ khi ông ta cung cấp lương thực cho họ." Ông ta bảo họ hãy đo đạc nguồn cung cấp, "Xin hãy chia phần đi." Nhưng khi thấy mình còn thiếu quá nhiều so với số khẩu phần cho mỗi người trong một ngày, ông ta thu gom dụng cụ hành lễ rồi rút lui. Còn về việc làm tướng lĩnh, ông ta không muốn nói gì thêm nữa.