Бой у ворот Ташкента отнюдь не являлся первым духовным контактом между Средней Азией и Россией, ибо религия, очевидно, способствовала официальным отношениям, связывающим стороны. Предположительно в 986 году киевские князья зондировали почву для своего обращения в ислам в Хорезме; шах выразил предварительно свое удовлетворение желанием русских принять ислам, одарил их богатыми подарками и послал одного из своих имамов обучить их исламским установлениям. Эти русские, свидетельствовали без иронии мусульманские историки, стали мусульманами благодаря «желанию обрести право вести войну за веру». Однако князь Владимир, согласно древнеславянской версии этой истории, отверг в 986 году учение мусульманских проповедников, заявив, что обрезание и неупотребление свинины и вина ему неугодно. Если, как соглашаются исламские и русские предания, посланцы из Азии и имели шанс распространить ислам, то они не смогли обратить русских в свою веру на данном решающем историческом этапе и таким образом упустили колоссальную возможность использования религии для привязки этой крупнейшей славянской народности к Востоку вместо Запада.
Хотя вопросы веры всегда окрашивали отношения между русскими христианами и мусульманами Средней Азии, по крайней мере до падения Ташкента религия никогда не являлась первоочередной проблемой в отношениях между сторонами, никогда не предпринимались «крестовые походы» с единственной целью обратить в иную веру население, проживавшее на конкурирующей территории. Это обусловливалось, видимо, тем, что после принятия Россией христианства Средняя Азия доминировала в ней лишь в качестве придатка монгольских властей в третьей четверти XIII столетия, а монголы в то время не желали распространения ислама в России. Вскоре после того, как крах Золотой Орды в XV веке позволил царям раздвинуть границы своей территории в направлении Сибири, Россия начала продвижение в сторону недавно образовавшегося ханства, союзного Бухаре. Хотя русских привела туда не антипатия к мусульманам, это преднамеренное предприятие стало для двух сторон религиозным состязанием, так же как первой пробой политических сил, настроившей азиатское ханство против Москвы.
Бухарский хан Абдалла (правление 1557–1598) отправил в 1572 году в Сибирь религиозную миссию с целью укрепления ислама, а в 1598 году в послании своему протеже, сибирскому хану Кучуму (пр. 1563–1598), еще раз подчеркнул религиозное значение защиты Сибири от русских: «Врагами нашей веры в настоящее время являются кафиры [русские]… тебе нужно заключить мир [с местными азиатскими вождями] и подумать о том, чтобы снова изъять твои земли из рук кафиров. Если ты не понимаешь этого сейчас… то останешься бессильным перед кафирами».
Кучум и Абдалла умерли вскоре после составления этого послания, а Россия продолжила поглощение Сибири, и хотя это столкновение создало напряжение в отношениях между Бухарой и Москвой, оно не воздвигло религиозных барьеров для дальнейшего общения.
Несмотря на отдельные конфликты между «верующими» и «неверными», как называли друг друга представители обеих религиозных конфессий, религия с самого начала стала важным государственным вопросом в отношениях между Россией и Средней Азией в связи с паломничеством и заключением браков. Эти ситуации спорадически повторялись в период, когда Астраханское ханство подчинилось России в XIV столетии и далее из-за русской оккупации через три столетия. Наиболее удобные пути для паломников из Средней Азии в Мекку проходили прямо через Персию, но они блокировались враждебными мусульманами шиитского вероисповедания, и теперь для суннитов была закрыта основная альтернативная дорога через территорию татарского Астраханского ханства. Поэтому мусульманам приходилось добиваться разрешения проходить по территории, удерживавшейся Россией, чтобы совершить продолжительное путешествие через Черное море в Стамбул, а оттуда в Мекку. Дипломатическая почта в Россию из Бухары и Хивы, особенно в XVII и XVIII веках, часто содержала просьбы об обеспечении беспрепятственного прохода мусульман в их Священный город. Как правило, русские неохотно давали такое разрешение. До указа Екатерины II от 9 мая 1780 года позиция царствующего дома относительно связей между мусульманскими странами оставалась негативной: «Одним из политических правил было… блокировать связи с единоверцами, как для мусульман, проживающих в границах империи, так и для мусульман, не являющихся подданными [России], населяющими Великую Татарию, через данную территорию, с Крымом, Кубанью и Оттоманской Портой».