Ifølge ledelsen i Kiev har Russland sendt 30 pansrede personellkjøretøy og 6.000 soldater over grensa.
Øyenvitner forteller at soldater vokter flyplasser, veier og offentlige bygninger, men hvem som er lokale og hvem som er russiske, er uklart.
Russland har fra før en enorm marinebase i Sevastopol på Krim-halvøya, der det skal befinne seg minst 15.000 soldater.
Bilder av russiske militærkjøretøy som ble tatt lørdag, var tatt i Balaklava som er en del av Sevastopol. Alt tydet på at soldatene var russiske, men det var uklart hvor de var på vei.
(Artikkelen fortsetter under bildet)
Selvstyre
Krim-halvøya har en stor grad av selvstyre, og regionens nyvalgte leder Sergej Aksyonov ba lørdag Russland om hjelp for å sikre ro og orden.
– Jeg har et ansvar for livet og sikkerheten til borgerne, og jeg har derfor bedt Russlands president Vladimir Putin om å hjelpe til med å sikre fred og ro på Krims territorium, sa han.
Den russiske nasjonalforsamlingen ga noen timer senere grønt lys til å intervenere militært, men Putin hevdet lørdag kveld at han ville avvente situasjonen før han eventuelt sender militære forsterkninger til Krim.
– Presidenten har ennå ikke fattet noen beslutning, understreket Putins talsmann Dmitrij Peskov.
Russiske interesser
I en 90 minutter lang telefonsamtale med USAs president Barack Obama fastholdt Putin at Russland forbeholder seg retten til å beskytte russiske interesser i Øst-Ukraina.
Et flertall av befolkningen på Krim-halvøya er etniske russere og den russiske svartehavsflåtens har hatt sin base i Sevastopol siden 1783.
Den nåværende leiekontrakten for basen ble inngått av nylig avsatte president Viktor Janukovitsj i 2010, som et ledd i en byttehandel som sikrer Ukraina billig naturgass fra Russland.
Den såkalte Kharkiv-avtalen, som løper til 2042, utløste sterk kritikk fra de proeuropeiske kreftene som nylig grep makten i Kiev. De har truet med å annullere hele avtalen og jage bort den russiske svartehavsflåten alt i 2017.
Tilbake til forlegningene
President Barack Obama erkjente tidligere i uka at Russland har spesielle interesser og kulturelle og økonomiske bånd til Ukraina, og han ga uttrykk for forståelse for at ledelsen i Moskva ser med uro på maktskiftet som har funnet sted i Kiev.
Under lørdagens 90 minutter lange telefonsamtale med Putin, var tonen tøffere. Obama minnet om hvilke forpliktelser Russland har i henhold til FN-charteret og ba ifølge Det hvite hus Putin kalle de russiske soldatene tilbake til forlegningene på Krim-halvøya.
Obama foreslo samtidig å sende internasjonale observatører fra FN og Organisasjonen for sikkerhet og samarbeid i Europa (OSSE) til området, for å sikre tryggheten til de etniske russerne på Krim.