Олег не думал исполнять договора и являться в Киев на княжеский съезд. Вместо того он явился в Смоленск (где тогда неизвестно каким путем сел брат его Давид), набрал там войска и, вышедши оттуда, пошел вниз по Оке, ударил на Муром, который достался в управление сыну Мономаха Изяславу, посаженному на княжение в соседней ростовской земле. (Отец Олега Святослав, сидя в Чернигове, был в то же время на княжении и в Муроме, и потому Олег считал Муром своею отчиною). 6 сентября 1096 года Изяслав был убит в сече. Олег взял Муром и оковал всех найденных там ростовцев, 6елозерцев и суздальцев: видно, что князь Изяслав управлял муромцами при помощи людей своей земли. В Муроме и его волости в то время еще господствовало язычество; край был населен народом финского племени, муромою, и держался за князьями только посредством дружины, составлявшей здесь, вероятно, еще единственное славянское население в те времена. В Ростове, Суздале и Белозерске, напротив, славяно-русская стихия уже прежде пустила свои корни, и эти края имели свое местное русское население.
Олег, отвоевавши Муром, взял Суздаль и поступил сурово с его жителями: одних взял в плен, других разослал по своим городам и отнял их имущество. Ростов сдался Олегу сам. Возгордившись успехами, Олег затевал подчинить своей власти и Новгород, где на княжении был другой сын Мономаха Мстислав, молодой князь, очень любимый новгородцами. Новгородцы предупредили покушение Олега и, прежде чем он мог встать с войском на новгородской земле, сами отправились на него на ростовско-суздальскую землю. Олег убежал из Суздаля, приказав в досаде сжечь за собою город, и остановился в Муроме. Мстислав удовлетворился тем, что выгнал Олега из ростовско-суздальской земли, которая никогда не была уделом ни Олега, ни его отца; предложил Олегу мир и предоставлял ему снестись со своим отцом.
Мстислава располагало к уступчивости то, что Олег был его крестным отцом. Олег притворно согласился, а сам думал внезапно напасть на своего крестника; но новгородцы узнали об его намерении заблаговременно и вместе с ростовцами и белозерцами приготовились к бою. Враги встретились друг с другом на реке Колакше в 1096 году. Олег увидел у противников распущенное знамя Владимира Мономаха, подумал, что сам Владимир Мономах пришел с большою силою на помощь сыну, и убежал. Мстислав с новгородцами и ростовцами пошел по его следам, взял Муром и Рязань, мирно обошелся с муромцами и рязанцами, освободил людей ростовско-суздальской области, которых Олег держал в городах Муроме и Рязани пленниками; после того Мстислав послал к своему сопернику такое слово: "Не бегай более, пошли с мольбой к своей братьи; они тебя не лишат русской земли". Олег обещал сделать так, как предлагал ему победитель.