К концу XVIII века деревня Рыбная была приписана к приходу Михаило-Архангельского храма села Долговского, находившегося в 15 верстах . В середине XIX века в Рыбной имелась часовня. Не позднее 1901 года была построена деревянная церковь и открыт самостоятельный Рыбновский приход, находившийся в ведении Оренбургской кафедры. Возможно, храм действовал в начале 1930-х годов и в нем служил священник Максимилиан Власов (арестован в 1932 году). О дальнейшей судьбе храма сведений нет.