Sju demonstranter greps över en natt utanför immigrationskontoret där hon hölls fången.
Guadalupe Garcia de Rayos, 36, mor till två amerikanska barn, korsade södra gränsen från Nogales, Arizona vid 10:00 lokal tid.
Protester hade försökt blockera fordon som transporterade henne, men kunde inte.
På onsdag kväll blockerade demonstranterna, som fruktade hennes deportation under president Donald Trumps ingripande mot invandringen, en skåpbil som tros bära Ms de Rayos.
Det var ett av flera fordon som stoppades från att lämna immigrations- och tullmyndighetens (ICE) centrum på onsdag kväll.
"Att se min mamma i bilen var oförklarligt. Det var verkligen hjärtdroppar," hennes dotter Jaqueline sa under en presskonferens efter utvisningen tillkännagavs.
"Ingen ska någonsin gå igenom smärtan av att få sin mamma borttagen från dem, eller smärtan av att packa hennes resväska," den 14-årige sade genom tårar.
Enligt amerikanska medier arresterades Ms de Rayos 2008 under en räd på hennes arbetsplats och dömdes för identitetsstöld för innehav av falska papper.
Men hon fick fortsätta att bo i Arizona så länge hon checkade in med sitt lokala ICE-kontor i Phoenix var sjätte månad, tillägger rapporten.
Läs mer om president Trumps immigrationsorder:
Förbjuden: En irakisk familjs invandringshistoria
Är USA på väg mot en konstitutionell kris?
Är Trumps immigrationsorder laglig?
Det var under denna check in på onsdag som hon togs i förvar, bara några dagar efter Donald Trump undertecknade en exekutiv order bredda reglerna enligt vilka vissa människor kommer att deporteras.
Där föreskrivs att alla papperslösa invandrare som dömts för brott skall prioriteras vid utvisning.
"Vi lever i en ny era nu, en era av krig mot invandrare," Ms de Rayos advokat, Ray A Ybarra Maldonado berättade New York Times.
"Ms Garcia, som har en tidigare brott fällande dom i Arizona för brottslig imitering, var föremål för en domstol utfärdat borttagningsorder som blev slutlig i juli 2013," en talesman för USA: s invandring och tullverkning berättade BBC.
Trots överklaganden ansåg domarna "att hon inte hade någon rättslig grund för att stanna kvar i USA", sade Yasmeen Pitts O'Keefe.
"ICE kommer att fortsätta att fokusera på att identifiera och ta bort personer med fällande domar som har slutgiltiga beslut om avlägsnande utfärdat av landets invandringsdomstolar", lade hon till i ett skriftligt uttalande.
Dussintals aktivister samlades utanför centrum i ett försök att blockera fordon från att lämna, många av dem skanderar "rättvisa".
Polisen sa att sju personer hade arresterats "utan våld" men att de flesta av demonstranterna var "fredliga och utövade sina rättigheter på rätt sätt".
Mr Trumps långtgående verkställande order har också avbrutit vidarebosättning av flyktingar och blockerat individer från sju majoritetsmuslimska nationer från att komma in i USA.
Flytten utlöste många protester i USA och över hela världen, liksom flera rättsliga utmaningar, även om den amerikanska allmänheten tycks vara jämnt splittrad i frågan.
Reseförbudet stoppades så småningom förra veckan och en amerikansk appellationsdomstol kommer att meddela sitt beslut om huruvida den verkställande ordningen var berättigad eller inte under de kommande dagarna.
En mexikansk kvinna som hade bott i USA sedan 14 års ålder har deporterats till Mexiko, immigrationstjänstemän har berättat för BBC.