В 1123 году князь Всеволод женился на дочери Черниговского князя святого Николая Святоши, из дома Ольговичей. И когда родился у него сын — первенец Иоанн, князь построил в 1127 году в честь его Ангела церковь святого Иоанна Предтечи на Опоках с приделом во имя святого пророка Захарии. На имя этой церкви благочестивый князь около 1135 года дал особую уставную грамоту, сохранившуюся до наших дней. В грамоте читается: «Вот, я, князь Всеволод, нареченный во Святом Крещении Гавриил, сын Мстиславов, внук Володимира Мономаха, благоволением Божиим поставил церковь святаго Иоанна Великаго на Петрятине дворище, и снабдил ее иконами многоценными и всеми книгами, и устроил попов и дьякона, и дьяка в соборной церкви». Новопостроенная церковь назначается быть приходской церковью особого торгового товарищества, которое называлось по ее имени «купечеством Иванским». Для заведения делами церкви и всего товарищества избиралось из среды его пять старост. Главный доход церкви составлялся из торговых пошлин, именно — из платы за употребление весов и мер, которые хранились в церковном притворе. Пошлины эти служили главным источником содержания церкви и служившего при ней духовенства. Из тех же доходов платилось и духовенству, приглашенному совершать богослужение в храмовые праздники. На праздник Рождества святого Иоанна Предтечи здесь служит Новгородский владыка, на другой день — архимандрит Юрьевский, на третий — игумен из Антониева монастыря. Грамота точно исчисляет, сколько кому из высшего духовенства следует дать вознаграждения за эти службы и какие вообще выдачи следует производить по случаю праздника.
Богобоязненный князь Всеволод был вместе с тем и мужествен. Преданный своему долгу, он высоко ценил чувство чести и не оставлял безнаказанным дерзких врагов его удела. Сохранился доселе огромный меч святого Всеволода с надписью: «Чести моей не уступлю никому». С этим мечом изображается он и на иконе.
Великим постом 1123 года князь Всеволод вынужден был предпринять поход против северных соседей Новгорода — ями. Враги были побеждены. Но возвращение войска в Новгород было очень затруднительно. Снег растаял и дороги испортились, не хватало продовольствия. Тем не менее поход окончился счастливо.
В 1130 году Всеволод с двумя своими братьями Изяславом и Ростиславом ходил на финское племя эстов. Враги были жестоко наказаны: многих перебили, жилища сожгли, детей и женщин забрали в плен и привели на Русь. Но в следующем году потребовался новый поход под предводительством уже одного Всеволода. Эстонцы сражались храбро, побили многих новгородцев. Еще ранее, в 1127 году, святому князю Всеволоду пришлось идти по воле отца на непокорного князя полоцкого Давида Всеславича, который и лишен был стола. Полоцкие князья с их женами и детьми взяты были в плен великим князем Мстиславом и отправлены в Царьград к византийскому императору. Так протекло 15 лет княжения Всеволода в Новгороде.
В 1132 году умер отец его великий князь Мстислав, и для Всеволода начался ряд тяжелых испытаний, которые почти не прекращались до самой его кончины. Причинами этого были общие в нашей земле тогдашние неустройства и усобицы князей. Вступив на великокняжеский престол после своего брата Мстислава, князь Ярополк немедленно, в том же 1132 году, вызвал князя Всеволода из Новгорода в Переяславль, считавшийся старшим после Киева. Новгородцы отпустили князя с неудовольствием. Между тем младшие сыновья Мономаха, Георгий и Андрей, не захотели, чтобы в преемники великому князю Ярополку предназначался племянник их Всеволод и решили изгнать его из Переяславля. Утром Всеволод въехал в Переяславль, а к обеду оставил его, избегая междоусобия, и отправился опять в Новгород. Но здесь встретили его недоброжелательно. На вече в Новгород пришли псковичи и ладожане. Вече сильно волновалось и не приняло князя Всеволода. Всеволод оставил Новгород, однако граждане скоро одумались, вернули князя Всеволода, но, по-видимому, ограничили его в правах и власти.
Тем временем Новгородские пригороды подверглись нападению чуди, и по возвращении в Новгород святой Всеволод в 1133 году ходил в Эстонию, ограждая границы Новгородские, и взял город Юрьев, или Дерпт.