Arseny Yatsenyuk sade regeringen var att skicka ett lagförslag till parlamentsledamöter som uppmanar att Ukrainas icke-bloc status annulleras.
Anförandena kommer när Nato håller ett krismöte för att diskutera krisen i östra Ukraina.
Väst har intensifierat sina anklagelser om direkt rysk inblandning i konflikten, efter framsteg av proryska rebeller.
I torsdags släppte Nato satellitbilder som visade ryska styrkor i Ukraina. Och sa att mer än 1000 soldater opererade där.
Ryssland förnekar att skicka trupper.
Nästan 2 600 människor har dödats sedan april, säger FN, när Rysslands annektering av Krim fick rebellerna att ta kontroll över stora delar av Donetsk- och Luhanskregionerna i den östra delen av landet.
"Regeringen skriver in en proposition till Verkhovna Rada [parliament] om upphävande av Ukrainas icke-bloc status och återupptagande av Ukrainas kurs för Nato medlemskap," Mr Yatsenyuk sade.
Ukrainas tidigare president Viktor Janukovitj, som fördrivits tidigare i år, fastställde landets alliansfria status i konstitutionen 2008.
Vid ett regeringsmöte sade Yatsenyuk att Ukrainas främsta mål fortfarande var medlemskap i Europeiska unionen.
Han sade att det lagförslag som lades fram också skulle hindra Ukraina från att ansluta sig till vilket block som helst som skulle stå i vägen för detta, dvs. varje ekonomisk union som inbegriper Ryssland.
Tunga strider pågår nära Ukrainas strategiska hamn i Mariupol, vid Azovhavet. Rebellstyrkor försöker fånga staden men ukrainska regeringsstyrkor gräver sig in.
På torsdagen intog separatisterna den närbelägna staden Novoazovsk.
Framsteget har väckt farhågor om att Kreml kan försöka skapa en landkorridor mellan Ryssland och Krim - ett territorium annekterat av Ryssland från Ukraina i mars.
Rebeller rapporteras också ha omringat regeringssoldater på flera platser längre norrut, nära staden Donetsk.
Ukrainska styrkor nära staden Ilovaysk säger att de är avskurna och har enträget bett om förnödenheter och förstärkningar.
Över en natt uppmanade Rysslands president Vladimir Putin rebellerna att öppna en "humanitär korridor" för att tillåta inringade ukrainska trupper att ge sig av utan onödiga förluster, även om han inte angav platsen.
Rebelledaren Alexander Zacharchenko berättade senare för rysk TV att hans soldater hade gått med på begäran, under förutsättning att ukrainarna lämnar över tunga vapen och ammunition.
Ukrainas säkerhetstjänstemän sade i ett uttalande att förslaget visade att rebellerna "leds och kontrolleras direkt från Kreml".
Minst 2 593 personer hade dödats i konflikten mellan mitten av april och den 27 augusti, sade FN i sin senaste rapport.
Kränkningar av mänskliga rättigheter som bortförande och tortyr "upptogs främst av de väpnade grupperna", som hänvisar till rebellerna, sades det.
Avskilt sade Human Rights Watch i en rapport att rebellerna utsatte civila för tortyr, förnedrande behandling och tvångsarbete.
Rapporterna om ryska trupper som stred mot rebeller föranledde förnyad västerländsk kritik av Moskvas roll i konflikten.
USA:s president Barack Obama skyllde på Ryssland för upptrappningen men slutade med att säga att dess trupper hade invaderat Ukraina.
"Det råder ingen tvekan om att detta inte är ett inhemskt uppror i östra Ukraina", sade han.
"De separatister utbildas av Ryssland, de är beväpnade av Ryssland, de finansieras av Ryssland."
Barack Obama kommer att diskutera krisen med de europeiska ledarna vid ett Nato-toppmöte i Storbritannien nästa vecka.
Nato släppte satellitbilder den sa visade kolumner av ryska väpnade styrkor inne i ukrainska territoriet.
Nato Brigadgeneral Niko Tak sade att mer än 1.000 ryska trupper var verksamma i Ukraina, både stödja separatisterna och slåss på deras sida.
Han sade till BBC att det hade skett en "betydande upptrappning av nivån och förfiningen av Rysslands militära inblandning i Ukraina" under de senaste två veckorna.
Rysslands utrikesminister Sergei Lavrov sade att inga bevis hade lagts fram för att Ryssland var direkt involverat.
"Vi hör olika gissningar, inte för första gången, men inte en enda gång har några fakta presenterats för oss", berättade han för journalister.
Vid torsdagens krismöte i FN:s säkerhetsråd accepterade Rysslands ambassadör Vitaly Churkin att det fanns ryska frivilliga i östra Ukraina, men anklagade Ukrainas regering för "krig mot sitt eget folk".
Ukrainas premiärminister har sagt att han kommer att be parlamentet att sätta landet på en väg mot Nato-medlemskap.