Sachverhalt: A. X._ hätte die Schweiz nach dem rechtskräftigen Entscheid des Bundesamtes für Flüchtlinge per 25. Juli 2002 verlassen müssen. Dies tat sie nicht. Am 27. Januar 2011 wurde sie wegen rechtswidrigen Aufenthaltes verurteilt. Die Anklage wirft der Angeschuldigten vor, sich zwischen dem 23. Dezember 2010 und dem 5. Oktober 2011 weiterhin widerrechtlich in der Schweiz aufgehalten zu haben. B. Das Bezirksgericht Brugg verurteilte die Angeschuldigte wegen rechtswidrigen Aufenthaltes zu einer unbedingten Freiheitsstrafe von drei Monaten und widerrief die bedingte Geldstrafe von 180 Tagessätzen zu Fr. 30.-- vom 27. Januar 2011. Das Obergericht des Kantons Aargau hiess die Berufung der Angeschuldigten am 21. August 2012 gut und stellte das Strafverfahren gegen sie ein. C. Die Staatsanwaltschaft Brugg-Zurzach erhebt Beschwerde in Strafsachen. Sie beantragt, den angefochtenen Entscheid aufzuheben und die Angeschuldigte entsprechend dem Urteil des Bezirksgerichts Brugg zu verurteilen. Eventualiter sei die Sache zur neuen Beurteilung an die Vorinstanz zurückzuweisen. D. Das Obergericht des Kantons Aargau verzichtet auf eine Stellungnahme. X._ beantragt, die Beschwerde sei abzuweisen. 