Sachverhalt: A. Das Bezirksgericht Aarau verurteilte A._ am 12. Februar 2018 wegen Diebstahls, Sachbeschädigung und Hausfriedensbruchs zu 12 Monaten Freiheitsstrafe, als Gesamtstrafe mit einer im Umfang von 6 Monaten aufgeschobenen Freiheitsstrafe gemäss Urteil vom 14. Juni 2017, deren bedingten Vollzug das Bezirksgericht widerrief. Ausserdem ordnete es eine Landesverweisung von 6 Jahren an. Auf Berufung von A._ hin bestätigte das Obergericht des Kantons Aargau am 11. Februar 2019 das erstinstanzliche Urteil im Schuldpunkt, reduzierte aber die Gesamtfreiheitsstrafe auf 10 Monate und die Landesverweisung auf 5 Jahre. B. Mit Beschwerde in Strafsachen beim Bundesgericht beantragt A._, der angefochtene Entscheid sei hinsichtlich der Landesverweisung sowie der vorinstanzlichen Kostenregelung aufzuheben und zu neuer Entscheidung zurückzuweisen. Er ersucht um unentgeltliche Rechtspflege. C. Obergericht und Oberstaatsanwaltschaft des Kantons Aargau verzichten auf eine Stellungnahme.