Sachverhalt: A. Y._ zeigte ihren Ehemann, X._, wegen häuslicher Gewalt bei der Staatsanwaltschaft Basel-Stadt an, die ein Strafverfahren eröffnete. Am 26. Mai 2011 beantragte Y._ die Sistierung des Verfahrens für die Dauer von 6 Monaten. Da das Begehren nach Ablauf der Frist nicht widerrufen wurde, stellte die Staatsanwaltschaft das Verfahren am 20. Dezember 2011 ein und auferlegte X._ die Verfahrenskosten von Fr. 1'029.--. Weil die Staatsanwaltschaft die Kostenauflage nicht begründet hatte, hiess das Appellationsgericht des Kantons Basel-Stadt am 29. Mai 2012 eine Beschwerde von X._ gut und wies die Sache zur neuen Beurteilung an die Staatsanwaltschaft zurück. Am 22. Oktober 2012 hielt diese an ihrem Kostenentscheid fest. B. Das Appellationsgericht wies die Beschwerde von X._ am 7. Mai 2013 ab. C. X._ führt Beschwerde in Strafsachen und beantragt, der Ent0scheid sei aufzuheben. Die Kosten seien dem Staat aufzuerlegen, und er sei mit Fr. 368.85 zu entschädigen. Eventualiter sei die Sache zur neuen Entscheidung an die Vorinstanz zurückzuweisen. Er ersucht um unentgeltliche Rechtspflege. Das Appellationsgericht und die Staatsanwaltschaft beantragen die Abweisung der Beschwerde, soweit darauf einzutreten sei.