Satelliterna avfyrades på en Soyuzraket från Franska Guyana.
Deras lyckade placering i omloppsbanan ger antalet plattformar i konstellationen till 10 - en tredjedel av vägen till ett fullt nätverk på 30.
Uppskjutningen skedde kl. 02.08 GMT, med bekräftelse på satelliternas separation från raketens övre scen nästan fyra timmar senare.
Galileo är ett projekt som genomförs av Europeiska kommissionen, EU:s verkställande avdelning.
Den är utformad för att komplettera American Global Positioning System (GPS), samtidigt som den ger extra precision för användarna.
Även om särskilda tjänster baserade på det europeiska nätet inte kommer att göras tillgängliga förrän minst 14 operativa satelliter är i omloppsbana, kan signalerna från varje nytt tillskott i luften utnyttjas genom att ta emot enheter med kompatibla chipsets.
"Det finns ett antal chipset som har utvecklats och finns på marknaden i smartphones och navigationsutrustning för bilar, till exempel," förklarade Javier Benedicto, Galileo programchef vid Europeiska rymdorganisationen (Esa är EU:s inköpsagent).
"Dessa chipset redan kan kombinera Galileo-signalerna med GPS-signalerna. Som omvandlas till en förbättring av tillgången på navigationstjänsten som GPS-användare upplever idag."
Utvecklingen av en "europeisk GPS" har varit en svår väg.  Projektet är flera år försenat, och kostnaden för slutförandet - förväntas bli cirka 7 miljarder euro till 2020 - är betydligt högre än vad som ursprungligen planerades av EU:s medlemsstater.
Men Didier Faivre, navigationschef på Esa, sa att leveranskadensen som avtalades 2013 bibehölls.
"Den berömda "30 satelliter till 2020" motto är vårt mål, och vi är övertygade om att vi kan göra det med ytterligare upphandling initieras i år," sade han BBC News.
Satelliterna för Galileo tillverkas av ett tysk-brittiska konsortium. OHB System of Bremen är den industriella huvudentreprenören och monterar varje rymdbuss, eller chassi.  Navigationen nyttolaster, inklusive atomuren som är kärnan i alla sat-nav koncept, är förberedda i Guildford av Surrey Satellite Technology Limited.
Konsortiet kör nu ut två satelliter var tredje månad.
Ett par väntar för närvarande på att skickas till Franska Guyanas Kourou rymdport från Esas testcenter i Nederländerna för ytterligare en Soyuz lansering i december. En ytterligare duo (dessa skulle vara nummer 13 och 14) kommer snart in i sluttest innan också skickas till Kourou.
Esa planerar bara en uppskjutning 2016, skicka upp en kvartett satelliter på den mycket större Ariane 5 raket. År 2017 skulle förmodligen se två uppskjutningar - ett par rymdfarkoster upphöjda av Soyuz, och en annan kvartett på en Ariane.
Hittills har EG bara beställt 26 satelliter, så den kommer snart att behöva beställa mer om den vill uppnå det magiska antalet 30. Men nästa upphandling kommer med största säkerhet att kräva mer än fyra plattformar på grund av problem med tre rymdfarkoster som redan befinner sig i omloppsbana.
Det är ännu inte klart om denna trio kommer att kunna ta deras plats i den slutliga konstellationen.  En hade ett strömavbrott och kan inte längre sända på alla sina frekvenser, och de andra två sattes i en felaktig omloppsbana av deras Soyuz raket.
Ingenjörer planerar att göra ändringar i Galileos marksystem för att ta hänsyn till dessa brister, men det är inte säkert att dessa ändringar kommer att göra det möjligt för de skadade satelliterna att ta på sig en fullt fungerande roll i nätet.
Jonathan.Amos-INTERNET@bbc.co.uk och följ mig på Twitter: @BBCAmos
Europa har satt upp ytterligare två rymdfarkoster i sitt satellitnavigeringssystem Galileo.