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

Далее, восстанавливая происхождение боярина Добрыни, мы обратимся к гипотезам историков, которые за неимением точных летописных сообщений зиждутся на логических предположениях.

Некоторые историки склонны считать, что Малко — это не кто иной, как бывший древлянский князь Мал, победитель и виновник гибели князя Игоря, мужа княгини Ольги, и несостоявшийся ее жених, которого после разгрома древлян княгиня держала в почетном плену в Любече.

Другая версия связывает происхождение Малко Любечанина не с древлянским князем, а с воеводой правителей Киева Игоря, Ольги, Святослава и его сына Ярополка — варягом Свенельдом. Летопись сообщает о сыновьях Свенельда — Мстиши и Люте (не исключено, что это был один персонаж — Мстиша-Лют или Мстислав Лютый). Ряд историков считают возможным полагать, что Добрыня и Малуша были детьми Мстиши или Люта-Мстиши и внуками Свенельда. Свенельду князь Игорь пожаловал дань с части Древлянской земли, а возможно, и еще с неких других юго-западных своих владений, т. к. по летописным известиям Свенельд принимал участие в подчинении Киеву восточнославянского племени уличей, живших на юго-западе Руси. Свенельд был богатым человеком, содержал собственную дружину, причем ее экипировке, по «Повести временных лет», завидовали «отроки» (воины младшей дружины) самого киевского князя Игоря. После гибели Игоря в ходе древлянского восстания 945 г. Свенельд командовал киевскими войсками в удачной для киевлян битве с древлянами. В дальнейшем он сопровождал воинственного князя Святослава в большинстве его походов и был главным советником и воеводой киевского князя Ярополка Святославича в 972–977 гг.

Былинные прозвища Добрыни Малковича — Резанович и Низкинич (от последнего и произошло «отчество» Никитич) — связывают Добрыню с известным боярским родом Резановичей с юго-западной части Руси — Волыни. Здесь Резановичами связано 3 больших села Калусов (совр. Гряды) Будятичи и Низкиничи . Интересно, что слово «Низкиничи» — это синоним «Маловичам», т. е. производное от «малого», «маленького», что в данной ситуации возвращает нас к мысли об имени древлянского князя Мала. Может быть, волости Будятичи и Низкиничи были пожалованы экс-князю Малу княгиней Ольгой вместо отобранной у него в 945 г. Древлянской земли, куда были направлены киевские наместники. (Будятичи в Никоновской летописи названы «селом Ольги».) С селом Будятичи ряд историков, в частности известный ученый XVIII в. В. Н. Татищев и современный украинский исследователь Ю. Диба , связывают место рождения племянника Добрыни — будущего великого киевского князя Владимира. В Будятичи Ольга, по сообщению Никоновской летописи, отправила «в гневе» находящуюся на сносях ключницу Малушу, там и появился на свет Владимир. С селом Калусовом деда князя Владимира и отца Добрыни Мала (Малко) связывает то прозвище, под которым этот исторический персонаж фигурирует у известного «Записками о Московии» автора начала XVI в. Сигизмунда Герберштейна, — Калюсча Малец.