Половцы-то и примчались на своих резвых лошадях к осаждённому Биляру с известием: булгары, сделав вылазку, разбили под Суваром войско Ярослава. Такая же участь постигла под Булгаром и Давыда, который совершенно растерялся во время вражеской вылазки, совершенной темной ночью.
Олег оставил Биляр и бросился на помощь братьям. Булгарский военачальник Килсар действовал ловко и смело. Сначала он заманил в ловушку половцев, увлёкшихся грабежом булгарских селений по берегам реки Камы, затем неожиданно напал на войско Олега и обратил в бегство всю его пехоту. Лишь благодаря железной стойкости конных полков удалось отбросить воинов Килсара.
После таких неудач Давыд и Ярослав совсем упали духом, настаивая на возвращении домой. Олег же упрямо стоял за продолжение войны, считая для себя делом чести победить булгар. Однако разлад среди половецких ханов вынудил его прекратить войну.
В конце концов Олег сам увяз в половецких склоках, пытаясь сподвигнуть степняков к новому вторжению. Он всю осень провёл в половецких станах, перекочёвывавших с летних пастбищ на свои зимние стоянки. Ханы относились к Олегу с неизменной благосклонностью: он знал их язык и обычаи. Однако от нового набега на булгар предводители донских половецких орд наотрез отказывались. Самый могущественный хан Шарукан подговаривал своих соплеменников к набегу на Переяславское княжество, где сидел юный Ростислав Всеволодович. Прочие ханы более склонялись попытать счастья с Шаруканом, нежели с Олегом.
Из лукоморских половцев воевать с булгарами согласился лишь хан Осолук, но и тот выдвинул условие: Олег должен взять в жены одну из его дочерей. Осолук давно знал Олега, вместе с ним хан ходил походом на Русь в пору, когда Олег с братом Романом пытались силой отнять Чернигов у Всеволода Ярославича. С той самой поры хан Осолук и возымел желание породниться с Олегом, который, по его мнению, обязательно должен был стать первым князем на Руси благодаря своей храбрости и настойчивости в достижении цели.
Олег согласился взять в жены одну из дочерей Осолука при условии, что сам выберет кого захочет. Хан не стал возражать. У него было пять незамужних дочерей. Все были рождены хану его младшими жёнами. От трёх старших жён у Осолука было три сына и ещё четыре дочери, уже выданные замуж за половецких батыров.
- Сыновей у меня мало, князь, - сказал Олегу Осолук, - поэтому я разборчив в выборе мужей для своих дочек. Ведь зятья по степному обычаю как сыновья для тестя.
Олег остановил свой выбор на шестнадцатилетней Тухруз. Она единственная из дочерей не опустила взор перед ним и глядела прямо в глаза во время смотрин, словно говоря: «Выбери меня, князь. Не пожалеешь!»