С переходом Геннадия Николаевича в большую политику его поездки стали более эффективными политически. Селезнёв впитывал в себя знание жизни. Слушал. Ввязывался в разговоры. Разумеется, помощники записывали фамилии, адреса, насущные нужды избирателей, чтобы можно было помочь конкретным людям, и помощь потом, конечно же, приходила. Но заместитель председателя Госдумы и вновь идущий на выборы кандидат старался запомнить настроения людей, их отношение к переменам в стране. Он очень ответственно подходил к своей новой работе народного избранника и одного из руководителей избранников.
А Россия менялась на глазах. К моменту выборов в Государственную Думу РФ второго созыва определилась верхушка государственной власти в стране. Она неофициально состояла из 4 человек: президент (уже без вице-президента), председатель правительства, председатель Совета Федерации и председатель Государственной Думы Федерального Собрания РФ. Из этих людей лишь председатель правительства представлял собой главу только исполнительной власти. Вот он и ездил по регионам, чтобы где-то что-то ускорить, где-то кого-то поддержать, устроить нагоняй или вообще выгнать, кому-то помочь, у кого-то всё доподлинно разузнать о причинах неудач или где-то найти хороший опыт, годный для распространения. Три других человека отвечали за иное: президент олицетворял собой политическую власть, а председатели двух палат Федерального Собрания — законодательную. Думец Селезнёв потому и вслушивался и в речи выступающих на встречах, и в просьбы избирателей, чтобы понять, как с помощью законов строить новую Россию.
КПРФ добилась на декабрьских выборах 1995 года огромного успеха. За ее кандидатов проголосовали 15 432 963 человека, в результате коммунисты получили полторы сотни мандатов — более трети от возможного. Народ словно очнулся и понял, что его крепко обманули.
В январе 1996 года нужно было выбрать председателя Госдумы. Председатель КПРФ Г. А. Зюганов предложил на пленуме своей партии кандидатуру В. А. Купцова. Светлана Петровна Горячева хорошо помнит то время:
«…И против выступила только я. Аргумент был простой: если хотите, чтобы в общественном мнении сложилось представление, что КПРФ — это вчерашняя КПСС, что те кадры, которые разбежались из ЦК вместо того, чтобы спасать Великую страну, а ныне снова карабкаются во власть, то голосуйте за этого кандидата. Люди должны видеть, что компартия другая, что ошибки и просчеты предшественницы в будущем не повторятся. Я предложила кандидатуру Геннадия Николаевича Селезнёва — человека не запятнанного, с хорошей нравственной и профессиональной репутацией. Тогда в руководстве КПРФ еще было много думающих людей, вновь обсуждение — и большинство с этим согласилось. Так в том числе и с моей легкой руки Г. Н. Селезнёв стал председателем Государственной Думы».