С именем Добрыни связан также другой сюжет, а именно рассказ о его отъезде и неудавшейся женитьбе Алеши. Это, пожалуй, самая распространенная из всех русских былин. Она была записана свыше 160 раз. Это не значит, что данная былина — лучшая из всех. Но это значит, что по своему характеру и по своим достоинствам она отвечает самым широким народным вкусам.

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

Былины, в которых герой борется с каким-либо чудовищем, представляют собой особую группу, глубоко отличную от былин о сватовстве. Они объединяются не только общностью своей темы. Бросается в глаза, что все основные песни этой группы связаны с именами лучших, наиболее любимых героев русского эпоса. Сюда относятся былины о Добрыне-змееборце, об Алеше и Тугарине, об Илье Муромце и Соловье-разбойнике, об Илье Муромце и Идолище и другие.