Хотя официальной датой основания города Царицына, ныне Волгограда, считается 1589 год, но существует легенда, что появился город раньше — в 1556 году, во время походов на Астраханское ханство, правда не на нынешнем месте, а на волжском острове. Такая путаница часто встречается в истории волжских городов, которые кочевали с места на места, перебираясь с одного берега на другой, как Саратов или с волжского острова на берег Волги, как Хвалынск. Вполне возможно было такое развитие событий и в случае с Царицыным.
Храмы в то время обычно строили деревянные и они разбирались и перекочёвывали с места на место вместе с городками. В той же легенде говорится, что храм во имя Иоанна Предтечи был заложен по приказу Ивана Грозного, еще во время пребывания городка на острове. Документальных подтверждений этому нет. Но когда город Царицын перебрался на правый берег Волги в место слияния рек Волка и Царица, то самым первым православным храмом на новом месте стал деревянный храм во имя Иоанна Предтечи, возведенный 2 июля 1589 года.
Собственно считается, что храм стал самым первым зданием нового городка. Судьба многих деревянных зданий на Руси была одинакова — они погибали в огне пожаров, не стала исключением первая церковь Царицына, сгоревшая в 1599 году. Восстановили острог и храм только в 1615 году по указанию царя Михаила Федоровича, снова в деревянном варианте. А каменным храм стал в 1704 году благодаря повелению другого русского царя — Петра Первого, который не раз бывал в городе и молился в этом храме. До него в храме дважды бывал Стенька Разин.
Для возведения храма использовался кирпич бывшей ханской ставки Золотой Орды, более тысячи возов разобранных ханских зданий были перевезены в Царицын. Из-за этого позже возникла легенда, что мол храм возведён на месте ханской ставки. Здание церкви долгое время оставалось единственным каменным зданием Царицына, ибо начался строиться Санкт-Петербург, был издан указ о запрете на возведение каменных зданий, а все строительные материалы стали отправляться для возведения северной столицы. В середине XIX века несколько обветшалое здание было отремонтировано.