Anklagelserna om hårresande fiffel med röstfusk, mutor och väljare som utsatts för press har enligt den ryska centrala valkommissionen kommit in från båda håll i regionen, där Vladivostok är huvudort.
Söndagen val var en andra omgång sedan den Kremltrogne sittande guvernören Andrej Tarasenko inte lyckats nå 50 procent i första ronden. Han såg länge ut att förlora andra omgången mot kommunistpartiets Andrej Isjtjenko, som när 95 procent av rösterna hade räknats ledde med fem procentenheter. Men vips, när det officiella slutresultatet kom stod Tarasenko plötsligt på 49,55 procent mot Isjtjenkos 48,06 procent.
Isjtjenko hotade med att gå till domstol och organiserade en demonstration i Vladivostok i måndags.
"Kriminellt gäng"
Kommunistpartiets nationella ledare Gennadij Ziuganov gick också i taket och kallade de lokala myndigheterna och valförrättarna för ett "kriminellt gäng".
- Man måste göra en utredning och dra allvarliga slutsatser, sade Ziuganov på onsdagen, och lade till att valet var ett "kriminellt drama".
Många av valen i Ryssland anmäls för att på olika sätt vara riggade. Men när det gällde Primorje Kraj vidtog centrala valkommissionen den ovanliga åtgärden att rekommendera att det ogiltigförklaras – något som myndigheterna nu alltså gjort. Enligt nyhetsbyrån Reuters är det första gången i "det moderna Rysslands historia".
Inom tre månader
Tarasenko själv säger att han accepterar beslutet, eftersom det har varit "för många klagomål". Kremltrogna medier hyllar i sin tur ogiltigförklarandet som ett bevis för att myndigheterna vill ha rena val.
Nu ska ett nytt val hållas i regionen inom tre månader.
Ett lagförslag om höjd pensionsålder samt ökad fattigdom i spåren av de utländska ekonomiska sanktionerna mot Ryssland har fått president Vladimir Putins popularitet att dala.
Också i regionerna Chabarovsk, Chakassien och Vladimir misslyckades Kremltrogna kandidater med att vinna i första omgången. Där ska den andra valomgången hållas på söndag.
Fakta: Ryska pensionsreformen
Den ryska regeringens lagförslag anger den nya pensionsåldern till 60 år för kvinnor och 65 för män, från nuvarande 55 respektive 60 år. Enligt det ursprungliga förslaget, som president Vladimir Putin efter all kritik korrigerade, skulle pensionsåldern för kvinnor vara 63 år.
Den förväntade livslängden i Ryssland är 77 år för kvinnor och 65 år för män, enligt 2015 års siffror, jämfört med 85 respektive 81 i Sverige.
2,9 miljoner ryssar hade den 25 augusti skrivit under ett upprop mot reformen.
Stödet för president Vladimir Putin i opinionsundersökningarna har minskat med omkring 15 procentenheter efter att planerna publicerades.
Putin lovade innan han blev omvald att inte röra pensionsåldern.