Sachverhalt: A. Die Staatsanwaltschaft Basel-Landschaft führte gegen X._ ein Strafverfahren wegen Schändung und Vergewaltigung sowie Widerhandlungen gegen das Ausländergesetz. Am 17. September 2012 stellte sie das Verfahren hinsichtlich der Sexualdelikte ein, entliess den amtlich bestellten Verteidiger und verweigerte X._ Entschädigungs- und Genugtuungszahlungen. Die wegen der Nebenfolgen erhobene Beschwerde hiess das Kantonsgericht Basel-Landschaft teilweise gut. Es wies die Staatsanwaltschaft an, X._ Frist zur Geltendmachung seiner Genugtuungs- und Entschädigungsansprüche zu setzen. B. Mit Strafbefehl vom 31. Januar 2013 wurde X._ wegen mehrfacher, teilweise versuchter Widerhandlungen gegen das Ausländergesetz zu 60 Tagessätzen zu Fr. 30.-- sowie zu einer Busse von Fr. 500.-- unter Anrechnung von 34 Tagen Untersuchungshaft verurteilt. C. Am 27. Februar 2013 wies die Staatsanwaltschaft die wegen des Strafverfahrens der Schändung und Vergewaltigung geltend gemachten Entschädigungs- und Genugtuungsansprüche von X._ unter Hinweis auf den rechtskräftigen Strafbefehl ab. Die hiergegen erhobene Beschwerde hiess das Kantonsgericht teilweise gut. Es sprach X._ für die erstandene Untersuchungshaft eine Genugtuung von Fr. 2'700.-- zu und wies die Schadensersatzansprüche ab. D. Die Staatsanwaltschaft führt Beschwerde in Strafsachen und beantragt, Ziff. 1 des Beschlusses des Kantonsgerichts vom 15. April 2013 aufzuheben und ihre Verfügung vom 27. Februar 2013 vollumfänglich zu bestätigen. E. Das Kantonsgericht und X._ beantragten die Abweisung der Beschwerde.