1996 йылдың 22 авгусында Бойондороҡһоҙ Дәүләттәр Берләшмәһенә инеүсе дәүләттәр менән хеҙмәттәшлек буйынса Рәсәй Федерацияһы министры итеп тәғәйенләнә. Күҙәтеүселәр фекеренсә, был тәҡдим Тулеев 1997 йылға тәғәйенләнгән Кемерово өлкәһе губернаторы һайлауҙарында ҡатнашмаһын өсөн эшләнә. Әммә 1997 йылдың яҙ-йәйендә хәл-торош үҙгәрә: өлкәлә киң күләмле пикеттар һәм митингылар үтә, өлкә башлығы Кислюктың популярлыҡ кимәле бик түбән була. Шундай шарттарҙа Кремль башлығы үҙе Тулеевҡа өлкә башлығы булырға тәҡдим итә.