За месяц до президентских выборов — 19 мая 1996 года — в Петербурге выбирали губернатора. Это были самые конкурентные выборы главы города за всю его историю. На второй срок шёл Анатолий Собчак. Главными конкурентами мэра были его заместитель Владимир Яковлев, всё ещё популярный в городе Юрий Болдырев и кандидат РПЦ-Яблоко — депутат Заксобрания Игорь Артемьев.
Пока Собчак заклеивал город агитационными плакатами, Яковлев строил вокруг себя коалицию. Он заключил с Артемьевым союз: тот снялся незадолго до первого тура и публично поддержал Яковлева перед вторым в обмен на сотрудничество после победы. Благодаря этой поддержке (а также блестяще проведённым дебатам) заместитель мэра с небольшим отрывом выиграл выборы. После выборов Яковлев сдержал обещание и сделал Артемьева первым вице-губернатором — так РПЦ-Яблоко пришла в исполнительную власть Петербурга.
После выборов команда РПЦ-Яблоко заняла несколько постов в администрации Санкт-Петербурга. Игорь Артемьев стал первым вице-губернатором и главой Комитета финансов, Алексей Чумак возглавил Комитет по транспорту, кроме них члены РПЦ-Яблока получили несколько постов заместителей Комитетов. Сотрудничество с губернатором продолжалось два с половиной года.
За это время яблочникам удалось многое сделать: городской бюджет из дефицитного сначала стал бездефицитным, а потом и профицитным; структура доходов и расходов бюджета стала прозрачнее; снизили налоги — увеличилась их собираемость; вводили новые автобусные и трамвайные маршруты; помогали пенсионерам, ветеранам и малоимущим.