Начиная с весны 1856 года Сайго вошел в близкий круг вассалов Нариакира, тех людей, которые были напрямую связаны с решением самых важных вопросов политики и экономики Сацума. Его ранг и стипендия по-прежнему оставались скромными, но он регулярно встречался со своим даймё и стал заметной фигурой в политике княжества. В 1857 году Нагаока Кэнмоцу, высокопоставленный вассал из княжества Кумамото, отметил, что Сайго, «хотя и является чиновником невысокого ранга, получает аудиенции у своего господина», в ходе которых Нариакира делится с ним мыслями о национальной политике. Кэнмоцу также нашел Сайго исключительно преданным, сконцентрированным и не склонным к праздной болтовне. 4/1857 Сайго сопровождал Нариакира в Кагосима, но 10/1857 Нариакира, желавший иметь надежного агента в Эдо, направил его обратно в столицу. Теперь от Сайго ожидалось, что он будет исполнять желания своего господина, находясь от него на расстоянии около тысячи миль. Если бы у Сайго возник вопрос, то ответа на него ему пришлось бы Ждать несколько недель. Вассалы Сацума, проживавшие в Эдо, имели дело с этим временным разрывом на протяжении веков, но ситуация, в которую попал Сайго, была значительно более трудной. Поскольку Нариакира бросал вызов установившемуся порядку, Сайго не мог полагаться на традиционные решения. Вместо этого он должен был угадывать реакцию своего господина на самые непредсказуемые ситуации. Сайго не уклонялся от возложенной на него задачи, но при этом находил свое положение крайне изматывающим. В письме своим дядям от 29/1/1858 он написал: «Последние дни были особенно трудными. Меня непрерывно осаждали люди, желавшие получить четкие указания». Узнав из письма, что его действия совпадали с планами Нариакира, Сайго испытал такое большое облегчение, что «плакал несколько часов».

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

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

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

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

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

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