Деревня Вахрушево носит фамилию первого переселенца, приехавшего сюда из европейской части России. В это время территория нынешней деревни и ее окрестности были сплошь заняты дремучим лесом, болотом, трясинами. Вахрушев и прибывшие с ним крестьяне постепенно « обживались», приспосабливались к условиям Сибири.

Вахрушев, по воспоминаниям старожилов, был зажиточным крестьянином. Позже сюда съезжались крестьяне из разных губерний России: Тамбовской, Оренбургской, с Украины и из Пензы, из Курской губернии. Не исключена возможность, что предками нынешних жителей села являются бежавшие или сосланные сюда участники восстания Степана Разина (1675-1676 г.), бежавшие в Сибирь старообрядцы, преследуемые царизмом участники восстания Булавина и Пугачева.

В 1903 – 1904 годах недалеко от д .Вахрушева был основан поселок «Оренбургский» приехавшими сюда крестьянами из Оренбургской и Тамбовской губернии.

Название поселку было дано на сходе жителей. Старожилы вспоминают, что название поселку давалось в горячем споре. Пришельцы Тамбовской губернии настаивали, чтобы поселок назывался «Тамбовский» однако большинство голосов оренбургских переселенцев одержало «победу». Ныне этот поселок ликвидирован, и все его жители переселились в д.Вахрушево.

В 1939 году рядом с деревней Вахрушево был найден скелет самки мамонта — первый полный скелет, обнаруженный на территории Западной Сибири. До этого в России полные скелеты мамонтов находили только на территории вечной мерзлоты.

Скелет нашли на берегу реки Оеш во время купания школьники Петя Глебов и Миша Мыльников. Палеонтологи назвали мамонта Матильдой, в настоящее время скелет Матильды хранится в Новосибирском краеведческом музее. На подъезде к деревне Вахрушево Коченёвского района открыт памятный камень в честь найденного неподалёку скелета мамонта. Останки ископаемого животного, найденного в пойме реки Оёшь, пролежали в земле 26 тысяч лет.

Рядом с Вахрушево также найдено погребение андроновцев, относящееся к бронзовому веку. Андроновцы появились на территории Коченёвского района в XIII веке до н. э., вытеснив кротовцев, самусьцев и окуневцев. Могильник состоит из одних ссожжений, то есть умершие были кремированы. Согласно основной версии археологов кремация применялась для погребения храбро сражавшихся в бою воинов. На основании этого сделан вывод о большом количестве военных столкновений в данном районе.