После нападения на Аморга в Иасе Феримен вернулся в Милет, в то время как спартанский наварх Астиох по-прежнему находился на Хиосе, отрезанный от своих кораблей афинским флотом с Самоса. Примерно в начале ноября 412 г. до н. э. Тиссаферн прибыл в Милет, чтобы выплатить обещанные спартанцам деньги: каждый моряк получил месячное жалованье в размере одной аттической драхмы за каждый день службы. При этом Тиссаферн объявил, что в дальнейшем будет платить лишь половину от этой суммы, но Гермократ, неуемный командующий сиракузян, сумел добиться компромисса, и сумма жалованья немного возросла.
Хотя Алкивиад не принимал участия в этих спорах, после битвы при Милете он вновь сменил хозяев, уйдя от спартанцев и примкнув к Тиссаферну. Всеобщая настороженность по отношению к нему возникла среди пелопоннесцев «после смерти Халкидея и после сражения при Милете» (VIII.45.1). Афинский перебежчик тесно сотрудничал с Халкидеем, но после того, как спартанский военачальник погиб в бою, Алкивиад остался без важнейшей поддержки. Примерно в это же время подошел к концу срок Эндия на посту эфора, что лишило Алкивиада еще одного влиятельного друга, помощь которого пришлась бы очень кстати, ведь теперь Алкивиад «был во враждебных отношениях с Агисом и вообще казался человеком, не заслуживающим доверия» (VIII.45.1). Происхождение, личные качества и биография Алкивиада всегда вызывали подозрения, но ни один древний автор не поясняет, почему пелопоннесцы, находившиеся тогда в Ионии, вдруг поверили в его связь с изменниками и стали настаивать на том, чтобы Астиоху было отправлено письмо с приказом убить Алкивиада.
Вероятно, причина этой перемены заключалась в провале того плана, который Алкивиад выдвинул в Спарте. Афиняне сумели быстро подавить выступления в своих заморских владениях; Хиос, вместо того чтобы стать центром и источником всеобщего восстания, был осажден и оттягивал на себя пелопоннесские ресурсы. Судя по всему, Алкивиад также убедил спартанцев сыграть на руку персам. Персы не спешили выплачивать спартанским воинам обещанные деньги, а теперь и вовсе собирались урезать жалованье. Именно по совету Алкивиада Халкидей заключил с персами договор, который был невыгоден Спарте и, казалось, признавал за Дарием право на порабощение греков. Под Милетом афиняне нанесли пелопоннесцам поражение в сухопутной битве, в которой от наемников Тиссаферна было мало толку. Пелопоннесское войско под началом Феримена не разбило афинян, а лишь оказало услугу Тиссаферну, отдав ему в руки Аморга и Иас.
Скорее всего, Алкивиад решил сменить хозяев после того, как узнал о письме с приказом убить его, поэтому, когда в начале ноября Тиссаферн прибыл в Милет, Алкивиад уже несколько недель как находился при нем. Фукидид сообщает, что Алкивиад стал «руководителем Тиссаферна во всем» и что Тиссаферн «доверился ему вполне» (VIII.45.2; 46.5). Однако перс сам обладал острым и изощренным умом и имел свои причины для покровительства двойному беглецу.
Для Тиссаферна, как и для спартанцев, ситуация складывалась вопреки ожиданиям. Поскольку стремительного распространения мятежа в афинских владениях не произошло и быстрой победы не состоялось, войну нужно было вести дальше. Это требовало наличия крупного войска, а также большого количества денег, часть из которых, если не все, Тиссаферну пришлось бы выложить из собственных средств. У Алкивиада имелись ценные связи в обоих лагерях, и он мог быть полезен при контактах с ними, выступая от имени Тиссаферна. В свою очередь, сам Алкивиад нуждался в персидском сатрапе как в защитнике. Кроме того, сношения с ним наделяли Алкивиада определенным статусом: его служба в качестве доверенного, близкого и очень нужного советника человека, который способен решить исход войны, могла открыть для него возможность однажды вернуться в Афины. Пока же Алкивиада устраивало то, что он постоянно находится подле Тиссаферна, производя впечатление, что тот к нему прислушивается, точно так же как Тиссаферна устраивала ситуация, при которой Алкивиаду было позволено вести себя именно таким образом.
Помимо всего прочего, Алкивиад давал Тиссаферну советы относительно стратегии. Так, он предложил ему «не очень торопиться с окончанием войны и отказаться от желания предоставить одному государству владычество на суше и на море». Лучше всего было бы «предоставить эллинам истощать самих себя» (VIII.46.1–2). По-видимому, он вновь лишь озвучивал прописные истины, ведь у персов в Эгейском море не было собственного военного флота, с помощью которого можно было выиграть войну. Что касается использования финикийского флота, то здесь мы впервые слышим о подобных планах. Неясно, вынашивал ли их когда-нибудь Тиссаферн, но к началу зимы 412/411 г. до н. э. никакого финикийского флота, которым можно было бы воспользоваться, не существовало.