Вернувшись в Эдо, Сайго начал выполнять тонкую политическую задачу, которая заключалась в оказании влияния на выбор наследника сёгуна по двум направлениям: женские покои сёгуна и императорский двор. В Киото его главным союзником в продвижении кандидатуры Кэйки был Хасимото Санаи, вассал Мацудайра Сингаку. Сайго и Хасимото впервые встретились в 1855 году, но тесное сотрудничество между ними началось только 12/1857, по просьбе их даймё. Нариакира лично дал Сайго указание работать вместе с Хасимото. Нариакира написал Мацудайра Сингаку, что в целях продвижения кандидатуры Кэйки он может считать Сайго своим собственным вассалом. Некоторые считают, что это распоряжение сделало Сайго подчиненным Хасимото, который был на шесть лет его младше. Поначалу Сайго относился к Хасимото с осторожной почтительностью.

Так, например, 14/12/1857 он попросил Хасимото составить описание Кэйки в виде набора «тем для обсуждения», который они смогут использовать, лоббируя его кандидатуру в сёгунате и при дворе. Но очень скоро они стали близкими партнерами. В последующие годы Сайго описывал Хасимото как равного себе по рангу: «Я служил Фудзита Токо как своему господину, но Хасимото я поддерживал как своего товарища». Когда через двадцать лет Сайго принял смерть на склонах Сирояма, при нем было письмо от Санаи.

Хасимото открыл Сайго совершенно новый взгляд на Японию. Хотя Нариакира, как и Хасимото, высоко ценил достижения западной технологии, он открыто противостоял требованиям Соединенных Штатов о заключении торгового договора. Хасимото же, напротив, утверждал, что Японии нужны такие договоры для получения доступа к западной технологии. Соединив такие традиционные японские добродетели, как человеколюбие, справедливость, преданность и сыновняя почтительность, с иностранной «техникой и технологией», Япония с" может стать серьезной силой в международной политике. Как и Сайго, Хасимото считал себя учеником Фудзита Токо, но отрицал ксенофобию учения Мито. Япония может свободно учиться у Запада, пока она сохраняет собственные культурные традиции. Этот уверенный и оптимистичный взгляд на будущее Японии повлиял на формирование собственных взглядов Сайго. В последующие годы он говорил своим ученикам, что изучение иностранных обычаев будет помогать Японии до тех пор, пока оно сочетается с уважительным отношением к собственным традициям.

В Эдо попытки Сайго продвинуть кандидатуру Кэй-ки были связаны с третьей женой сёгуна, Ацухимэ, которая была приемной дочерью Нариакира. Женитьба сёгуна на Ацухимэ стала триумфом для Нариакира, итогом многолетних политических интриг. Идея о том, что Иэсада должен жениться на дочери Сацума, впервые появилась на свет в 1850 году, после смерти второй жены сёгуна, но при реализации этого плана Нариакира столкнулся с многочисленными проволочками и широкой оппозицией. Так, например, союзник Нариакира, Токугава Нариаки, считал, что для сёгуна будет позором брать себе невесту из «княжества Сацума, враждебного Иэясу», а не из дружественного воинского дома. Кризис с внешнеполитическими договорами и землетрясение в Эдо в 1855 году также отсрочили этот брак. Наконец, 18/12/1856 Иэсада и Ацухимэ заключили брачный союз. Нариакира с самого начала планировал использовать этот брак для защиты своих политических интересов, и спор из-за наследования показался ему идеальной возможностью проверить эффективность новых связей. Одним из самых рьяных противников Кэйки была мать Иэясу, но теперь у его сторонников тоже появились свои агенты влияния в женских покоях.

Перспектива оказания давления на сёгунат через женские покои поначалу казалась многообещающей. Ацухимэ была ловкой и находчивой, и, кроме того, ей оказывала помощь Икусима, придворная дама, известная своим большим политическим опытом. Говорят, что Икусима сорила деньгами, но при этом обладала тонким чутьем, которое почти всегда позволяло ей распознать тайные замыслы своих противников. Но мать сёгуна, Хондзюин, была не менее грозным противником. Хотя Хондзюин поддержала женитьбу Иэсада на невесте из Сацума, она упорно сопротивлялась любому внешнему вмешательству в спор из-за наследования. 2/1858 Икусима доложила, что, когда Ацухимэ затронула тему наследования, Хондзюин дала ей решительный отпор. Иэсада еще слишком молод, чтобы беспокоиться о наследнике, а Кэйки слишком стар, чтобы стать приемным сыном, объявила она, и в любом случае этот вопрос не имеет никакого отношения к Симадзу. Ацухимэ проявила упорство и 4/1858 затронула эту тему в разговоре с самим Иэсада. Судя по всему, Иэсада согласился подумать об усыновлении Кэйки, но Хондзюин оборвала разговор, пригрозив совершить самоубийство. Стало ясно, что Сацума не сможет повлиять на спор о наследовании через женские покои.

Когда перспектива использования Ацухимэ отдалилась, Сайго сосредоточил свои усилия на императорском дворе. Это был беспрецедентный случай. Никогда раньше императорский двор не вмешивался в спор о наследовании в доме Токугава. Тем не менее сам сёгунат изменил традиции правления Токугава. 12/1857 сёгунат обратился с беспрецедентной просьбой об императорской поддержке во внешней политике и привлек императорский двор к переговорам о торговых соглашениях. Договор Харриса 1858 года, названный так в честь американского консула Таунсэнда Харриса, требовал от Японии открыть несколько портов для торговли с Соединенными Штатами и признать их экстерриториальность. Председатель совета старейшин сёгуната, Хотта Масаёси, не хотел подписывать этот договор, который он считал политически летальным, не заручившись предварительно широкой поддержкой. Хотта рассматривал санкцию императора как не более чем формальность, учитывая тот факт, что императорский двор за последние двести лет ни разу не противостоял сёгунату. 12/1857 Хотта отправил в Киото посланника, чтобы получить одобрение императора. Поскольку' сёгун признавал императора как ученого, а не как администратора, на роль посланника Хотта выбрал директора сёгунской академии. Посланник получил отказ. Хотта был ошеломлен и 2/1858 отправился в Киото сам. Таким образом, Хотта невольно создал прецедент вмешательства императора в дипломатию, которая традиционно была прерогативой сёгуната. Теперь сторонники Кэйки пытались заручиться поддержкой императорского двора в вопросе о наследовании самого титула сёгуна.

2/1858 Хасимото, покинув Эдо, отправился в Киото, где начал встречаться с императорскими придворными, чтобы добиться с их стороны поддержки кандидатуры Кэйки. Сайго, чувствовавший себя политически уверенным в Эдо, но ничего не знавший о политике Киото, был склонен отдать инициативу Хасимото. Общая стратегия Хасимото заключалась в том, чтобы связать поддержку императором договора Харриса с поддержкой кандидатуры Кэйки. Его аргументация выглядела следующим образом: если Япония просто подпишет договор Харриса, то для «варваров» это будет равносильно политической капитуляции. Однако молодой и энергичный сёгун, такой, как Кэйки, сможет с выгодой использовать возможности, предоставленные договором, и мобилизовать Японию против дальнейших уступок. Сайго прибыл в Киото через несколько недель после Хасимото и начал разрабатывать свою собственную сеть контактов. Главным союзником Сацума при императорском дворе был Коноэ Тадахиро, высокопоставленный придворный, породнившийся через свою жену с домом Симадзу. Коноэ, который носил высокий титул «министр левой стороны», пользовался всеобщим уважением при дворе. Для поддержания связи с Коноэ Сай-го пользовался услугами монаха Гэссё, чей храм был связан с домом Коноэ. Гэссё был необычной фигурой в политике. Он пользовался широкой известностью как настоятель Дзёдзюин, аббатства при храме Киёмидзу, и как талантливый поэт, но при этом не считался открытым сторонником императора. Однако, благодаря такому недостатку политического опыта, он был прекрасным кандидатом на роль курьера для деликатной корреспонденции, поскольку у него имелись благовидные, не связанные с политикой причины для встреч как с Коноэ, так и с Сайго. Гэссё содержал резиденцию в аббатстве Сокусюин в храме Тофукудзи, где находились могилы многих вассалов Сацума. Сайго и Гэссё могли встречаться, не вызывая подозрений, в часовне, расположенной на кладбище. Ну а с Коноэ Гэссё мог встречаться в храме Киёмидзу, где были похоронены многие члены семьи Коноэ.