Mithridates, düşünü gerçekleştirmek için MÖ 105 yılında tebdili kıyafet yaparak, yakın adamlarıyla bir keşif gezisine çıkar. Amacı Kapadokya, Galatya, Roma’nın Asya eyaleti, Bitinya ve Paflagonya’yı sırayla dolaşarak, siyasi ve askeri durumları yerinde görüp, fetih planları hazırlamaktır.

Bu keşif gezisinde uzunca bir zaman Sinop’tan ayrı kalan Mithridates’in öldüğüne inanılır. Bu arada kralın dostları ona ihanet eder, kraliçe Laodike’yi (Mithridates, tahta geçtikten sonra eski Pers adetlerine uyarak kızkardeşi ikinci Laodike ile evlenmiştir.) baştan çıkartırlar. Mithridates, sarayına döndüğünde bu durumdan haberdar olur, hainleri ve karısını toptan ortadan kaldırtır.

MÖ 104 yılında Romalıların Kimbri istilasıyla uğraşmasını fırsat bilen Mithridates ile Bitinya Kralı Nikomedes Euergetes anlaşarak, iki uçtan Paflagonya üzerine yürümeye başlarlar. Her biri kendi tarafındaki Paflagonya topraklarını ele geçirdikten sonra Galatya’ya da saldırıp aralarında paylaşırlar. Roma’nın bu fetihlere ses çıkarmamasını sağlamak için Mithridates, Roma’daki Senato üyelerine açıktan açığa pek çok altın dağıtmıştır.

Kapadokya’yı zapt etmek için Nikomedes, MÖ 102 yılında Mithridates’ten önce davranır. Kapadokya sınırını aşan Bitinya ordusunu gören Kapadokya Kraliçesi Laodike (Mitridates’in ablası olan büyük Laodike’dir. Kapadokya Kralı Ariarathes Epiphanes Filopator ile evlenmiş, ancak kocasının MÖ 111 yılında asilzadelerden Gordios tarafından öldürülmesi üzerine henüz çocuk olan oğlunun naipliğine geçmiştir), Bitinya Kralı ile mantık evliliği yaparak her iki krallığın birleşmesini sağlar. Kapadokya’nın Bitinya’ya ilhak olmasını kabul etmeyen Mithridates, yeğeninin tahtını korumak bahanesiyle Kapadokya’ya girip Bitinyalıları oradan kovar. Yeğeni Ariarathes Filometor’u MÖ 100 yılında Mazaka’da tahta geçirir. Ancak genç kral Ariarathes, Pontus’a sığınmış olan babasının katili Gordios’un memleketine dönmesine itiraz etmesi üzerine, iki ordunun gözü önünde, görüşme talep eden bizzat dayısı Mithridates tarafından hançerlenerek öldürülür.

Mithridates, sekiz yaşındaki kendi oğlunu, Nisa’nın zehrinden kurtulmuş olan Kapadokya Kralı Ariarathes Eusebes Filopator’un oğlu diyerek tahta oturtur (Kapadokya kraliçesi Nisa, kocası savaş alanında öldükten sonra tahtı kaptırmamak için beş oğlunu art arda zehirleyerek katletmiş, altıncısı ancak kaçırılarak kurtarılmıştır. Zehirlenme olayı yirmi yıldan önce olduğu halde sahte prens henüz çocuktur). Mithridates, fiili idareyi Gordios’a bırakır.

MÖ 99 yılında Kapadokya’da meşhur Romalı general Gaius Marius ile görüşen Mithridates, ondan destek yerine nasihat alır: “Ya Romalılar kadar güçlü ol, ya da onlara boyun eğ!..” Mithridates bu nasihati hep dinlemiş, bütün hayatı boyunca Romalı kadar güçlü olmaya çalışmış, olamadığı yerde boyun eğmiştir.

Kapadokyalılar sahte krallarını bir isyanla kovup, yerine Ariarathesler hanedanının son prensi olan Ariarathes Epifanes’i (Bu prens, Mithridates’in öldürdüğü yeğeninin küçük kardeşidir) geçirirler. Mithridates bu duruma rıza göstermez ve Kapadokya’yı yeniden fetheder.

Kaçan kral kısa bir süre sonra hastalanarak ölünce Ariarathes hanedanı son bulur. Ancak Bitinya Kralı Nikomedes ile evlenmiş olan Laodike, Romalılara giderek, Ariarathes Epiphanes Filopator’dan bir oğlu daha olduğunu ve tahta onun oturması gerektiğini iddia eder. Mithridates de kendi uydurma iddiasını dile getirmek için Gordios’u gönderince, iki sahte prens Roma Senatosunda şiddetle savunulur.

Ne var ki Kimbri tehlikesinden kurtulan Roma, Pontus kralına Kapadokya, Galatya ve Paflagonya’dan; Bitinya Kralına da Galatya ve Paflagonya topraklarından çıkmasını bir ültimatomla bildirir. Durumun ciddiyetini anlayan Mithridates ile Nikomedes, zaptettikleri yerlerden çekilirler.