О связях половцев с мусульманами есть также сообщение, относящееся к еще более раннему времени. Согласно древнерусским летописям, в походе, организованном в 1184 г. ханом Кёнчэком (Кончаком), принимали участие мусульманские инженеры, обслуживавшие огнеметные и стрелометные орудия. В летописи они названы «бесоурмени» — термином, употреблявшимся в то время, как правило, по отношению к хорезмийцам.
Вообще для древнерусских летописей иногда характерно было называть как половцев, так и других степных кочевников, словом «измаильтяне», применявшимся, как правило, к мусульманским народам. Вероятно, здесь можно предполагать какой-то намек на значительное распространение среди западной части половцев ислама, хотя ни прямые данные письменных источников, ни материалы археологических раскопок не позволяют обоснованно судить об этом. Скорее всего, речь должна идти об особенностях мировоззрения летописцев, принадлежавших к той христианской традиции, где образ потомства Исмаила был наделен негативными свойствами и был обыгран в различных мифах.
Любопытен тот факт, что в родословной арских князей, упоминается имя некоего Бачман-султана, при этом его отец и дед носят арабские мусульманские имена. Если он идентичен Бачману, предводителю племени Ольберли, жившему в период монгольских завоеваний (см. след. главу), то это может свидетельствовать о распространении ислама среди части кыпчакской элиты, по крайней мере, в середине — второй половине XII в., но, с другой стороны, нет никакой уверенности ни в этой идентификации, ни в том, что эти поздние, созданные уже в мусульманской среде источники носят достоверный характер и к тому же не перенесли реалии своей эпохи на более ранние времена.
Волжская Булгария. Известно, что экспансия славянских племен приводила к вытеснению и ассимиляции ряда финно-угорских племен. Одним из конечных пунктов продолжавшейся экспансии на восточные лесные районы был в XI в. город Муром, хотя он еще в 1015 г. известен как подвластный киевскому князю город. По данным археологии, самобытная культура финно-угорского племени мурома начинает исчезать уже в этот период. Ряд финно-угорских племен входил, тем не менее, в сферу влияния Волжской Булгарии, и, чтобы не допустить дальнейшего расширения владений Руси, занятой в этот период больше делами на западном направлении, уже в 1088 г. булгары заняли Муром, однако, судя по всему, были вскоре выбиты оттуда. Булгарские правители понимали возможность дальнейшей экспансии князей, ставшей очевидным фактом уже в начале XII в., когда она разворачивается во всех направлениях. Не желая допустить дальнейшего расширения влияния Руси, в том числе захвата волжского торгового пути, булгарские правители предпринимают превентивные меры, сами переходя в наступление. Известно, что в 1107 г. один из подвластных им мордовских князей осадил и взял Суздаль.
В дальнейшем ростово-суздальские князья концентрируют свое внимание на восточном направлении, вступая в вековое противоборство с булгарами за контроль над верховьями Волги и политическое влияние над местными финно-угорскими племенами, такими как мари (черемисы) и мордва.
В 1117 г. половецкий хан Айоба (Аепа древнерусских летописей), тесть Юрия Ростово-Суздальского, сына Владимира Мономаха, вторгается в пределы Волжской Булгарии. Однако булгарский правитель вынужден был пойти на хитрость — он послал половцам отравленные пищу и питье, употребив которые, ничего не подозревающие половецкие предводители во многом числе умерли. В 1120 г. Юрий снаряжает против булгар собственный поход, также привлекая половецкие отряды союзных родов. В результате похода было захвачено множество добычи и пленных, после чего был заключен мирный договор, стабилизировавший общую границу.
О состоянии Волжской Булгарии с середины XII в. позволяют судить богатые данные археологических раскопок и записки арабского автора аль-Гарнати (1080—1169/1170), дважды побывавшего на территории Нижнего и Среднего Поволжья. По археологическим данным, в XI-XII вв. пределы этого политического образования простирались от р. Суры на западе до р. Шешмы на востоке, от Самарской Луки на юге, до района Елабуги на севере. Население этих территорий не было однородным в этно-лингвистическом и культурном отношении. Значительное распространение элементов мусульманской культуры в погребальной обрядности, характеризующейся достаточным единообразием, позволяет отчасти увязывать носителей этих признаков с доминирующей общностью, принадлежавшей к племенам тюркского круга. Арабский путешественник описывает город Булгар как окруженный деревянными стенами, люди жили в деревянных домах, но часть населения вокруг города жила в шатрах. Речь, несомненно, идет о кыпчаках и других тюркских племенах, селившихся в низовьях Камы, по данным археологии с конца XI в. булгарский правитель совершал зимние походы со своей закаленной армией на окружающие народы и накладывал на них джизью. Финно-угорское племя весь платило харадж. Те, кого арабский автор именует славянами (сакалиба), говоря о населении верховий Волги (хотя, возможно, речь идет о других финно-угорских племенах), также платили харадж булгарам. Поскольку харадж представлял собой поземельный налог, можно утверждать, что эти территории входили в прямое подчинение булгарского правителя, в отличие от земель других народов, власть над которыми ограничивалась сбором выплат в центральную казну. По-видимому, булгарские правители также сохраняли за рядом народов права на внутреннюю автономию.