Родился 27 мая 1953 г. в Новосибирске.
В 1974 г. окончил общеэкономический факультет Новосибирского института народного хозяйства (ныне - Новосибирский государственный университет экономики и управления "НИНХ") по специальности "экономист", в 1978 г. - аспирантуру Новосибирского государственного университета.
В 1974-1981 гг. работал стажером-исследователем, аспирантом кафедры политэкономии, ассистентом, старшим преподавателем Новосибирского государственного университета.
В 1981 г. преподавал политэкономию в Новосибирском институте народного хозяйства.
С декабря 1981 г. работал в плановой комиссии Новосибирского облисполкома: был начальником отделов промышленности и товаров народного потребления, планирования товаров народного потребления, затем заместителем председателя плановой комиссии Новосибирского облисполкома, заместителем председателя планово-экономического управления области. В феврале 1986 г. назначен первым заместителем начальника Главного планово-экономического управления Новосибирской области.
В апреле 1991 г. занял пост заместителя председателя исполкома Новосибирского городского Совета народных депутатов.
С января 1992 г. – первый заместитель главы администрации Новосибирска по вопросам экономической реформы, председатель городского комитета по экономике.
В 1992-1993 гг. - первый заместитель мэра г. Новосибирска Ивана Индинка.
В октябре 1993 г., после назначения Индинка руководителем Новосибирской области, Толоконский стал исполняющим обязанности главы города. В декабре того же года был назначен мэром Новосибирска.
24 марта 1996 г. он победил на первых выборах главы города, набрав 79,74% голосов избирателей. Его ближайший соперник, вице-президент по строительству производственного объединения "Сибтехпромстрой" Петр Лапков, получил 13,81%.
В 1994-1995 гг. и в 1999-2000 гг. Виктор Толоконский возглавлял Ассоциацию сибирских и дальневосточных городов.
В 2000-2001 гг. являлся членом Совета Федерации Федерального собрания РФ от Новосибирской области. Был членом комитета по вопросам экономической политики.
С 2000 по 2010 г. - глава администрации, губернатор (с января 2004 г.) Новосибирской области.
На выборах 19 декабря 1999 г. набрал 26,27% и вышел во второй тур вместе с заместителем министра экономики РФ Иваном Стариковым, за которого проголосовали 20,91% (оба были выдвинуты группами избирателей). 9 января 2000 г. был избран руководителем области, получив 44,32% голосов (Иван Стариков - 42,17%). Сменил на посту главы администрации Виталия Муху.
7 декабря 2003 г. Виктор Толоконский был переизбран главой администрации области, получив 57,67% голосов (баллотировался в порядке самовыдвижения). Второе место занял самовыдвиженец, предприниматель, Михаил Титов (17,80%).
12 июля 2007 г. Толоконский был утвержден главой администрации области новосибирским Советом депутатов по представлению президента РФ Владимира Путина.
2 декабря 2007 г. на выборах в Государственную думу РФ Виктор Толоконский баллотировался по списку "Единой России", возглавлял региональную группу №58 (Новосибирская область). После выборов от депутатского мандата отказался.
С 9 сентября 2010 г. по 12 мая 2014 г. занимал пост полномочного представителя президента РФ в Сибирском федеральном округе (сменил Анатолия Квашнина).
12 мая 2014 г. указом президента РФ был назначен временно исполняющим обязанности губернатора Красноярского края. Прежний руководитель региона Лев Кузнецов занял должность министра РФ по делам Северного Кавказа.
14 сентября 2014 г. одержал победу на выборах губернатора Красноярского края. Был выдвинут региональным отделением партии "Единая Россия", на выборах получил 63,30% голосов избирателей. Ближайший соперник Толоконского, председатель комитета по делам села и агропромышленной политике Законодательного собрания края, кандидат от КПРФ Валерий Сергиенко, набрал 14,01%. 26 сентября Виктор Толоконский официально вступил в должность.
29 сентября 2017 г. президент РФ Владимир Путин принял досрочную отставку Виктора Толоконского и назначил врио руководителя Красноярского края Александра Усса, председателя Законодательного собрания региона.
С ноября 2017 г. по май 2018 г. был советником Высшей школы государственного управления Сибирского института управления (филиала Российской академии народного хозяйства и государственной службы при президенте РФ).
В конце ноября 2017 г. назначен главным советником мэра Новосибирска (должность главы города занимал Анатолий Локоть). В июне 2018 г. уволился с поста.
22 июля 2020 г. назначен советником губернатора Новосибирской области Андрея Травникова.
С 6 марта 2023 г. - председатель совета директоров Международного выставочного центра "Новосибирск Экспоцентр".
Был членом президиума Госсовета РФ. Возглавлял рабочие группы по вопросам инновационного развития страны и развития национальной конкурентоспособности. Входил в состав межведомственной рабочей группы по вопросам федеративных отношений и местного самоуправления при комиссии при президенте РФ по вопросам совершенствования государственного управления.
Член партии "Единая Россия" (с 2005 г.).
Действительный государственный советник Российской Федерации I класса (2011).
Награжден орденами Дружбы (2001), "За заслуги перед Отечеством" IV степени (2008), Почета (2013), Александра Невского (2017). Отмечен благодарностями президента РФ (1996, 2003, 2005), почетными грамотами президента (2010) и правительства РФ (2003).
Кавалер ордена преподобного Сергия Радонежского I степени (РПЦ), Золотого Почетного знака "Общественное признание" (2001), лауреат национальной премии "Лучшие губернаторы России" (2002), премии им. Святослава Федорова, Общероссийской премии "Национальное достояние" (2007).