С 1997 года Анатолий Быков регулярно избирается в заксобрание Красноярского края. На выборах губернатора региона в 1998 году он поддержал Александра Лебедя, однако вскоре после победы последнего заявил, что "ошибся в нем как в губернаторе". Стороны вступили в открытый конфликт.
В марте 1999 года по итогам инициированной господином Лебедем проверки в отношении Анатолия Быкова было возбуждено уголовное дело о незаконном занижении энерготарифов в пользу Красноярского алюминиевого завода. Позднее добавились другие обвинения, и бизнесмен скрылся в Венгрии. В сентябре 1999 года Анатолий Быков мог стать вторым в избирательном списке ЛДПР на выборах в Госдуму, но ЦИК нашел в его декларации ошибки. Тогда же Александр Лебедь, комментируя новый компромат на господина Быкова, заявил: "Дракон убит".
1 января 2000 года бизнесмен написал письмо и. о. президента Владимиру Путину с подписью "Анатолий Быков, политический узник России в Венгрии". В послании он выразил надежду, что новый глава государства сможет "поставить на место зарвавшихся политиков". В апреле 2000 года бизнесмен был экстрадирован, и в июне 2002 года получил 6,5 года условно.
В сентябре 2002 года Анатолий Быков на губернаторских выборах поддержал проигравшего в итоге спикера краевого заксобрания Александра Усса. Ставшего губернатором Александра Хлопонина предприниматель даже спустя три года характеризовал так: "Для действий и поступков он еще молод".
17 февраля 2010 года Анатолий Быков не присутствовал в заксобрании на утверждении нового губернатора Льва Кузнецова. Вскоре соратник господина Быкова Валерий Усаков стал внештатным советником главы региона. В 2010-2011 годах Анатолий Быков и Лев Кузнецов неоднократно вместе выступали на общественных мероприятиях.
В марте 2012 года Анатолий Быков в открытом письме премьеру Дмитрию Медведеву заявил о готовности помочь "восстановить авторитет и правительства, и "Единой России"". Не получив ответа, он возглавил красноярское краевое отделение партии "Патриоты России". По итогам выборов 8 сентября 2013 года "патриоты" получили 14 мест в гордуме Красноярска против 12 у "единороссов".