Самых лютых своих ненавистников Добрыня сумел выпроводить из Новгорода и повод для того нашёл легко: почти все недовольные княжьим посадником оказались замешаны в бунте. Причём бунт был не против самого Добрыни, но против греческой веры, пятью годами ранее учреждённой князем Владимиром, то есть получилось, что бунтовщики покушались именно на княжескую власть. Бунтовщики подняли немало горожан, к ним легко и подозрительно быстро примкнула чернь из окрестных сёл. И запылали ярким пламенем терема многих новгородских христиан. Заговорщики едва не сумели поджечь и тринадцатиглавую Софию, но там их сумели остановить и не дали совершить задуманное...

Посадник, в недалёком прошлом опытный воевода, подавил бунт жёстко, но не жестоко, лишней крови проливать не стал, однако так или иначе убрал из Новгорода всех зачинщиков и наиболее отчаянных участников разбоя (само собою, тех, кто остался в живых). Остальные сразу поутихли. И шипение по поводу «рабынина братца» умолкло. Тем более что обидеть и уязвить этим Добрыню было невозможно. Смешно ему было стыдиться родства с матерью великого князя Киевского, а кем она была прежде, так кого ж это касается? Сами-то вы, любезные бояре, кто бы были без надёжной княжеской власти и твёрдой руки своего посадника?

Конечно, вспоминать историю появления своего при дворе прежнего князя Святослава Игоревича Добрыня не любил. Были они со старшей сестрой Младой детьми любечского княжьего дружинника Мала. Дружинник отличался нравом крутым и порой буйным, драться любил не только на бранной сече, но и в жизни мирной, притом по любому поводу. Как-то во время княжьего застолья Мал, хватив лишнюю чару хлебного вина, сошёлся в споре с другим дружинником, дошло до кулачной схватки, и тяжёлый кулак Мала, угодив в висок противника, отправил того в мир иной.

Князь пришёл в ярость, ибо всё случилось прямо у него под носом, дерущиеся так разошлись, что и княжьего окрика не послушались. И, как на беду, Мал в ту пору оказался совсем без денег — виру платить было нечем. Оставалось либо продавать себя в рабство родственникам убитого (их, как назло, оказалось много, и все голосистые и напористые!), либо как-то откупаться от них. Провинившийся дружинник не нашёл ничего лучше, чем предложить в качестве виры собственную дочь, семнадцатилетнюю красавицу Младу. Обиженные родственники с удовольствием на это согласились. Так старшая сестра Добрыни сделалась невольницей. Вскоре в Любеч наведался с дружиной сам князь Святослав Игоревич. Он приехал за данью, которую надо было выплатить, князь бывал очень крут с теми, кто платить не хотел, это знали уже во всех подвластных ему изначально и во многих завоеванных им землях. Любечский князь стряс княжескую дань со своих бояр, и среди подношений Святославу оказалась красивая молодая рабыня.

Князь Киевский остался доволен. Млада сразу ему приглянулась. Он забрал её с собой в Киев и, чтобы во время его частых военных походов девушка была под надёжным приглядом, подарил невольницу своей матери княгине Ольге.

Что до пятнадцатилетнего Добрыни, то он не захотел после этого оставаться с отцом, уехал из Любеча в Киев и сумел попасть в княжескую дружину. Был парень высок ростом, крепок, неплохо владел оружием и умел ездить верхом, а на то, что у него ещё не пробивается борода, как-то и не обратили внимания. Тем более что многие дружинники в то время, подражая князю, начисто брили бороды. Таким образом, Добрыня остался хотя бы вблизи любимой своей сестрицы да и служил исправно, так что спустя десять лет стал при князе уже воеводой.

Княгиня Ольга, так и не уговорившая своевольного сына принять крещение, очень скоро склонила к греческой вере и полюбившуюся ей Младу, и её брата. Они охотно сделались христианами. Поэтому, когда князь Владимир Святославович решился креститься сам и крестить весь подвластный ему народ русичей, Добрыня стал ему в том преданным помощником.

К тому времени, к концу десятого столетия по Рождеству Христову, на Руси было уже немало крещёных людей, во многих местах давно жили прочные христианские общины, были даже монастыри, так что задуманное князем дело оказалось хотя и трудным, но небезнадёжным.