Первые упоминания о населённом пункте, известном ранее как деревня Бычкова, относятся к XVIII веку. Современное название — Красноселка — закрепилось к концу XIX века. В 1903 году в деревне была построена церковно-приходская школа, а вскоре после этого обустроен небольшой молитвенный дом. В 1910 году, по решению сельского схода, началось строительство деревянной церкви во имя святого благоверного князя Александра Невского. Строительство завершилось в 1913 году, и первым настоятелем храма стал священник Аршин. На погосте у церкви был похоронен его сын Николай, умерший в младенчестве.
В 1935 году церковь была закрыта, и здание использовалось под зернохранилище. До 1975 года в церкви сохранялось 14 больших икон в иконостасе, однако затем всё было утрачено, и здание пришло в запустение. В январе 1988 года новокузнецким архитектором М. Т. Ледковым был подготовлен проект реставрации храма. Рассматривалась возможность переноса и реставрации церкви в музее-заповеднике «Томская Писаница» Яшкинского района, однако по просьбе жителей села здание было передано Русской Православной Церкви. В 1991 году настоятель Ильинского храма города Тайга совершил в нём первый молебен. Были отремонтированы фундамент, железная крыша, заново настелены полы и сооружено ограждение церкви.
Архитектурно храм представлял собой срубленный в «лапу» семиглавый храм начала XX века с традиционным набором объёмов по оси «запад-восток»: притвор-колокольня с двумя небольшими, примыкающими хозяйственными помещениями; прямоугольная в плане трапезная, соединённая с притвором дверным проёмом; храмовая часть, раскрытая из трапезной широким пятигранным проёмом; апсида. Храмовая часть была двухсветной, имела по северной и южной стенам выходы на улицу, оформленные в виде двухстворчатых дверей с крыльцом и навесом на резных столбах. Южный и северный фасады в уровне кровли заканчивались двумя небольшими фронтонами. Завершалась храмовая часть пятиглавием с большой центральной главкой, покрытой кровельной жестью. Окна храма были оформлены простыми деревянными наличниками. Объём колокольни был решён в три яруса, причём третий ярус — ярус звона — был раскрыт по четырём граням сквозными проёмами для колоколов. Каждая грань колокольни при переходе в шатёр украшалась маленьким треугольным фронтоном. Над восьмигранным шатром колокольни возвышалась маленькая главка с крестом.
В августе 1993 года первым настоятелем возрождённого храма был назначен священник Любомир Крохтяк. В 1994 году при храме действовала воскресная школа, в которой с 24 учениками проводила занятия матушка Мария Крохтяк. Стараниями настоятеля в 1994–1995 годах были покрыты железом купола, отреставрированы резные колонны иконостаса, написаны для него второй и третий ярусы икон, приобретена и установлена резная гробница, а во дворе устроен колодец.
