За эти три года Алкивиад участвовал в десятке битв, потопил или захватил 200 кораблей и огромную добычу и теперь мог вернуться в Афины победителем. Город встречал его как героя. Конфискованное по суду имущество Алкивиада было возвращено ему за счет казны, а жрецам было приказано снять с него проклятие. Но Алкивиад не доверял пылкой любви сограждан, понимая, что весь его авторитет держится только на военной славе, и достаточно малейшей неудачи, чтобы от него отвернулись.
Осенью 408 года до н э. он снаряжает новый поход – 100 триер, 1, 5 тысячи гоплитов и 150 всадников. Высадившись на острове Андросе, он наносит поражение отряду андросцев и их союзникам спартанцам. Но положение дел к тому времени изменилось не в пользу афинян. Противники еще копили силы и избегали решительных действий. Алкивиад также не стремился к решающему сражению и ограничивался небольшими стычками. Он держался очень осторожно, что вызывало недовольство в афинском обществе, ждущем от него громких побед. Ему часто приходилось покидать флот, чтобы добыть необходимые средства на его содержание. Во время одной из таких поездок, вопреки строжайшему запрету Алкивиада не вступать в боевые действия против Лисандра, афинский военачальник Антиох все-таки вступил в бой со спартанским флотом. Это произошло при Нотии, и Антиох попал в ловушку, расставленную Лисандром, и потерпел поражение, потеряв 15 кораблей. Узнав об этом, Алкивиад сразу же вернулся на Самос и пытался вызвать Лисандра на продолжение битвы, но спартанец от боя уклонился. Хотя поражение при Нотии никак не повлияло на ход военной кампании, оно дало повод противникам Алкивиада обвинить его в измене, настроив против него народное собрание.
Алкивиаду пришлось удалиться в добровольное изгнание во Фракию, где у него были построены три небольшие крепости. Однажды, когда афинский флот оказался в этих краях, Алкивиад, видя, как беспечно ведут себя на кораблях афиняне – отлучаются подолгу на берег, рассредоточивают корабли и так далее, – он решил предупредить их о последствиях такой беспечности, зная, что спартанский флот находится где-то рядом. Выслушав его, стратег Тидей велел ему убираться, сказав, что теперь он здесь не начальник. Но, к несчастью, произошло то, что предсказывал Алкивиад. Лисандр воспользовался беспечностью афинян и захватил афинский флот, а затем и Афины.
Алкивиаду снова пришлось покинуть свое убежище. Он направился к своему бывшему противнику, персидскому сатрапу Фарнабазу, «услуживая ему и вместе с тем пользуясь его уважением». Затем он решил ехать дальше, к персидскому царю Артаксерксу II, и предупредить его о заговоре, который готовили против него спартанцы и брат царя Кир. Он рассчитывал привлечь персидского царя на сторону Афин и с его помощью разгромить спартанцев и освободить город, где Лисандр установил власть «Тридцати тиранов».