Храм святого Александра Невского в селе Иртышск был построен вместе с основанием села в 1911 году. Освятил место под строительство и заложил первый камень епископ Омский и Павлодарский Владимир (Путята). Согласно документам, хранящимся в Иртышском историко-краеведческом музее, на церемонию закладки храма в августе 1911 года в Иртышск приехали сибирский генерал-губернатор из Омска, военный губернатор из Семипалатинска, омский архиерей и павлодарское уездное начальство. Сначала соорудили небольшую деревянную часовню, а потом в основание строительства будущей церкви лег первый кирпич, сделанный на местном кирпичном заводе. Храм строили на народные деньги - каждый сельчанин одну десятую часть своего дохода отдавал на строительство. Высота стен храма была более 12 метров, общая площадь - 200 квадратных метров.
Разрушение храма датируется 1933-1934 гг. Сняли купола, сбросили колокола. Очевидцы рассказывают, что при падении один из колоколов раскололся на мелкие кусочки. Позже здание храма отвели под мельницу. В 1970-е годы делались попытки разрушить храм совершенно, но стены так и не смогли сломать. Остались руины.
Приходская жизнь в Иртышске возобновилась в 1993 году. Временно было выбрано здание в центре села для проведения богослужений. В 2007 г. было принято решение восстанавливать дореволюционный храм. Три миллиона тенге на восстановление храма пожертвовал Глава Сбербанка России Герман Греф, который родился и вырос в Иртышском районе. В марте 2011 года было завершено строительство левого придела в честь иконы Пресвятой Богородицы «Спорительница хлебов».
27 марта 2011 года была совершена первая Божественная литургия. В старом помещении храма находятся библиотека, воскресная школа, трапезная.