I begge de to landene i Europas sør-østlige hjørne vant kandidater som utfordret det sittende regimet og lovte å orientere seg mer mot Russland.
Moldova er Europas fattigste land, mens Bulgaria er det fattigste av landene som er med i EU.
Den russiskvennlige generalen Rumen Radev fikk nesten 60 prosent av stemmene i Bulgaria, noe som førte til at statsminister Boiko Borisov umiddelbart trakk seg.
I Moldova fikk sosialistpartiets Igor Dodon 52,2 prosent av stemmene da andre valgomgang ble arrangert søndag.
– Selvfølgelig er vi imponert av noen av uttalelsene til vinnerkandidatene som indikerer at de har vilje til å arbeide med å normalisere forholdet til andre land, sa president Putins pressetalsmann Dmitrij Peskov ifølge nyhetsbyrået Interfax i dag.
Han kunne også fortelle at Putin har ringt og gratulert den nyvalgte bulgarske presidenten.
– En suksess for Russland
Bulgaria ble medlem av Nato i 2004 og av EU i 2007. Samtidig har landet historiske bånd til Russland, blant annet som fordi landene deler både det kyrilliske alfabetet og den ortodokse kirken.
Under valgkampen gjorde Radev et nummer ut av han ville bedre forholdet til Russland og Kreml sa seg raskt glade for seieren.
– Vi regner dette landet som svært viktig for oss, sa Kreml-talsmann Peskov.
I hvilken grad forholdet mellom Bulgaria og Russland vil endre seg etter valget er uklart.
Bulgaria har allerede tidligere sagt seg skeptiske til EUs sanksjoner mot Russland, og kan komme til å forsterke motstanden.
Samtidig synes det allerede klart at seieren til Radev ikke vil føre til at den skrinlagte gasslinjen «South Stream», som skulle gått fra Russland, gjennom Bulgaria, til Vest-Europa blir vekket til live igjen.
Kiril Avramov ved Det nye bulgarske universitetet mener at Russland allerede har vunnet en seier i Bulgaria ved at det nå stilles spørsmål ved Nato og EU.
– I lang tid var både EU og Nato lukkede temaer. Nå har det blitt åpnet for debatt og det er allerede en suksess for Russland, sier Kiril Avramov ved Det nye bulgarske universitetet, til Reuters.
Lover å stoppe handelsavtale
Mens Radev ikke har kommet med konkrete løfter om endringer i forholdt til EU og Russland, har Dodon i Moldova tatt klarere stilling for Russland.
Et av de sentrale løftene hans under valgkampen var å vrake en handelsavtale som EU og Moldova inngikk i 2014.
Handelsavtalen med EU førte til at Russland innførte handelsrestriksjoner, noe som har rammet Moldova hardt.
Etter seieren gjorde da også Dodon det klart at hvordan han så seieren og sa at folket hadde stemt for vennskap med Russland.