В ноябре 1907 года — новый, четвертый по счету арест. Баиловская тюрьма. Та самая, куда вскоре водворят и Сталина. Здесь они встретятся. Впервые? Нет, знакомство состоялось раньше — в июне 1906 года, в темной подвальной комнате женского училища, выходившей на бывший Михайловский (позже Плехановский) проспект. Здесь размещалась редакция большевистской газеты «Дро» («Время»), которой руководил Сталин. Следующая их встреча состоялась весной 1907 года в Баку, когда Серго вернулся из Берлина. И вот судьба снова свела их в одной тюремной камере.
В апреле 1908 года Орджоникидзе предстал перед особым присутствием тифлисской судебной палаты, заседавшем в Баку. Приговор был суров — лишение всех прав состояния и вечная ссылка в Сибирь. Но это было еще не все. Летом того же года этапным порядком его отправили в Батуми для суда по делу 1905 года, связанным с провозом оружия. Продержав в батумской тюрьме до сентября, власти направили его для суда в Сухуми. Там он получил дополнительно год заключения в крепости.
После отсидки — несколько месяцев пересылки с этапа на этап, из одной пересыльной тюрьмы в другую. Местом поселения Орджоникидзе была назначена деревня Потаскуй Пинчугской волости Енисейской губернии Приангарского края. Тмутаракань, конец света. Три черные избы с одной стороны просеки, четыре — с другой. Слева — стан Погорюй, справа — заимка Покукуй. Через два месяца после прибытия к месту вечного поселения Орджоникидзе своими руками сработал челн и рискнул отправиться на нем до глухой даже по сибирским понятиям заимки Дворец, откуда по едва заметной тропинке между двумя трясинами выбрался к первому жилью.
Беглец благополучно прибыл в Баку, а через некоторое время большевистская организация направила его в Персию, где под влиянием революции 1905–1907 годов вспыхнули массовые выступления беднейших слоев населения. Орджоникидзе возглавил боевую дружину, пришедшую на помощь повстанцам, участвовал в походе революционного отряда, выступившего против шахсеванских вождей. Находясь в Персии, Серго держал тесный контакт с Лениным, с заграничным большевистским центром. Он организовал транспорт заграничной большевистской литературы в Россию через Персию, вел систематическую переписку с Лениным, постоянно читал его газету «Социал-демократ».
В одном из ее номеров прочел короткое сообщение: в Париже готовится к открытию партийная школа, профессиональные революционеры смогут там пополнить свои теоретические знания. Возвратившись из Персии в Баку, он оттуда уезжает в Париж, где прямо с вокзала направляется на квартиру Ленина. «Раз приходит консьержка и говорит: «Пришел какой-то человек, ни слова не говорит по-французски, должно быть, к вам», — напишет впоследствии в своих воспоминаниях Н. К. Крупская. — Я спустилась вниз — стоит кавказского вида человек и улыбается. Оказался Серго. С тех пор он стал одним из самых близких товарищей».
Орджоникидзе становится вольнослушателем партийной школы в Лонжюмо, близ Парижа. Однако учебу вскоре пришлось прервать. По заданию Ленина он снова отправляется в Россию с ответственным поручением — провести работу по подготовке и созыву общероссийской партийной конференции. Серго еще не пересек границу Франции, а петербургская полиция уже располагала сведениями, что он командирован Лениным с особыми инструкциями в Россию. В Баку за ним была установлена неусыпная слежка, несколько раз он чудом ускользал из умело расставленных полицией сетей, но поручение Ленина выполнил, о чем и доложил ему, возвратившись в Париж. Итогом напряженнейшей работы стала партийная конференция в Праге, делегатом которой от тифлисской большевистской организации был Орджоникидзе. На первом же ее заседании он выступил с обширным докладом о работе, проделанной Российской организационной комиссией.
Из Праги в Петербург возвращался членом ЦК. В Вологде навестил ссыльного Сталина. Сообщил ему о создании бюро ЦК для руководства работой в России в составе Сталина, Орджоникидзе и Спандаряна. Сталин снялся с места ссылки и вместе с Орджоникидзе тронулся сначала в Баку, затем в Тифлис. Серго был нарасхват. Все хотели услышать о Пражской конференции из уст ее участника. После многочисленных докладов Орджоникидзе вернулся в Петербург.
Здесь ему крупно не повезло. Его снова арестовали. После шестимесячного предварительного заключения Петербургский окружной суд приговорил за побег из ссылки и за нелегальную работу к трем годам каторги с последующим водворением на место вечной ссылки. Закованный в кандалы прямо в зале суда, каторжный срок он отбывал в Шлиссельбургской крепости. Оттуда этапным порядком — в Якутию.