Следующий негативный след, который оставил Добрыня в истории древнерусского государства, связан с крещением Новгородской земли, куда он был послан Владимиром вместе с митрополитом Иоакимом. В немногочисленных литературных источниках, дошедших до нас, зафиксировано: «Добрыня крестил новгородцев огнем, а Путята мечом». В Новгородской летописи о крещении сообщается под 989 годом: «И прииде к Новугороду архиепископ Яким и требища разори, и Перуна посече, и повеле влещи в Волхов». Перуна, как и до того в Киеве, волокли по грязи, колотили жезлами и сбросили в реку.
Само собой разумеется, что подобное святотатство не могло не встретить яростный протест со стороны язычников. Но интересы внутренней и внешней политики киевского князя требовали, чтобы крещение русской земли прошло повсеместно и как можно быстрее. Эту важную задачу Владимир мог возложить только на Добрыню.
Узнав об этом, новгородцы поклялись Добрыню в город не пускать. Тщательно готовились они к встрече с бывшим союзником: разметали середину моста, с Софийской стороны поставили на нем два камнемета. «Со множеством камения поставища на мосту, яко на сущие враги своя», — отмечает литературный памятник. Верховный языческий жрец Богомил, прозванный за свое красноречие «Соловьем», собирал толпы горожан и проповедовал им, запрещая покоряться Добрыне. И тысяцкий Угоняй предостерегал: «Лучше нам померети, нежели боги наши дати на поругание». В этом бунте против воли правителя участвовали и верхи, и низы Новгорода. Но, несмотря на отчаянное сопротивление, несколько сот человек были все-таки окрещены силой.
Тем временем народ на Софийской стороне, за Волховом, не бездействовал. Начали громить богатых. Разорили дом Добрыни, убили его жену и еще кого-то из родственников. Разметали, разнесли по бревнышку церковь Преображения.
Посланник Владимира рассвирепел. По его приказу тысяцкий Путята с дружиной в 500 воинов переправился ночью через Волхов и устроил побоище. Утром вслед за ним отправился и Добрыня, к тому моменту уже нашедший способ покорить новгородцев. Он велел дружине поджечь дома горожан. В результате деревянный город выгорел дотла. Важно отметить, что язычники лишь «разметали» христианскую церковь, желая изгнать неприятелей с их территории. Добрыню же не остановила даже мысль о беспощадном пожаре. Зная о его непреклонности, новгородцы не стали дальше гневить «добра молодца» и попросили мира. Добрыня унял дружинников и уже беспрепятственно крестил город.
Чтобы лучше представить себе весь цинизм происходившего, следует обратиться к событиям, которые имели место совсем незадолго до этого. А именно: когда при поддержке новгородского боярства и купечества Владимир взял власть над Киевом, среди первых государственных дел князя было то, что принято называть «религиозной реформой». Летопись красноречиво свидетельствует об этом: «И стал Владимир княжить в Киеве один и поставил кумиры на холме за теремным двором: деревянного Перуна с серебряной головой и золотыми усами, затем Хорса, Дажьбога, Стрибога, Симаргла и Мокошь. И приносил им жертвы, называя их богами, и приводили к ним своих сыновей и дочерей, а жертвы эти шли бесам и оскверняли землю жертвоприношениями своими. И осквернялась земля русская и холм тот». В оставшийся без князя Новгород Владимир отправил своим посадником Добрыню. Летопись под 980 годом сообщает об этом: «Придя в Новгород, Добрыня поставил кумира над рекою Волховом, и приносили ему жертвы новгородцы как богу».
Таким образом, совершенно очевидно, что Владимир обманул ожидания как киевской, так и новгородской знати. Существует предположение, что своей «религиозной реформой» на начальной стадии княжества он делал уступки старой киевской знати, которая помогла ему сесть в Киеве. Существовала традиция, по которой новый князь должен был «обновить» обветшалые фигуры языческих божеств. По совету Добрыни Владимир сделал ставку на, говоря современным языком, консервативную партию, на сторонников традиционной идеологии, которые были сильнее. (Впоследствии его сын Ярослав тоже будет вынужден делать выбор. И он сделает ставку на сторонников новой веры в противовес консервативной партии, поставившей на Свято-полка.)