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