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.

Erwägungen:
1.
1.1. Der Beschwerdeführer rügt, der Kostenentscheid verletze <ref-law> und verstosse gegen die Unschuldsvermutung. Er habe die Einleitung des Verfahrens weder rechtswidrig und schuldhaft bewirkt noch habe er dessen Durchführung durch sein Verhalten erschwert. Das Verfahren sei einzig durch das Verhalten der Ehefrau zustande gekommen und hernach eingestellt worden. Er sei nie mit den Vorwürfen konfrontiert worden. Sein Anspruch auf rechtliches Gehör sei verletzt. Die Anzeige habe lediglich als Druckmittel in familienrechtlichen Verfahren gedient.
1.2. Die Vorinstanz erwägt, die Kostenauflage durch die Staatsanwaltschaft verletze kein Bundesrecht. Der Beschwerdeführer habe das Strafverfahren rechtswidrig und schuldhaft bewirkt. Aus den Berichten des Universitätsspitals ergebe sich, dass die Ehefrau über einen längeren Zeitraum häuslicher Gewalt und Bedrohung durch den Beschwerdeführer ausgesetzt worden sei. Am 16. März 2010 habe die Ehefrau gegenüber den Ärzten geäussert, körperliche Gewalt von Seiten des Beschwerdeführers erfahren zu haben, am 18. November 2011 [recte 18. November 2010] von ihm beleidigt, beschimpft, geschlagen und am 3. Dezember 2012 [recte 3. Dezember 2010] mit dem Tod bedroht worden zu sein. Die Vorinstanz präzisiert, dass diese Einträge in den aufgezählten Akten des Universitätsspitals Basel auf Angaben der Ehefrau beruhen. Keiner der sie behandelnden Ärzte habe Zweifel an ihrer Glaubhaftigkeit gehegt. Die Kostenauflage enthalte keine strafrechtliche Sanktion und verletze damit die Unschuldsvermutung nicht.
1.3. Die Einstellung des Verfahrens gestützt auf <ref-law> hat in der Regel eine Kostenauflage zu Lasten des Staates zur Folge (<ref-law>). Von dieser Regelung kann abgewichen werden, wenn das strafbare Verhalten des Täters bewiesen ist, was namentlich der Fall ist, wenn dieser geständig ist (Urteil des Bundesgerichts 6B_835/2009 vom 21. Dezember 2009 E. 4.3, mit Hinweisen).
Ansonsten können der beschuldigten Person die Verfahrenskosten ganz oder teilweise auferlegt werden, wenn sie rechtswidrig oder schuldhaft die Einleitung des Verfahrens bewirkt oder dessen Durchführung erschwert hat (<ref-law>). Nach der Rechtsprechung des Bundesgerichts verstösst eine Kostenauflage bei Freispruch oder Einstellung des Verfahrens gegen die Unschuldsvermutung gemäss <ref-law> und Art. 6 Ziff. 2 EMRK, wenn dem Angeschuldigten in der Begründung des Kostenentscheids direkt oder indirekt vorgeworfen wird, es treffe ihn ein strafrechtliches Verschulden. Damit käme die Kostenauflage einer Verdachtsstrafe gleich. Dagegen ist es mit Verfassung und Konvention vereinbar, einem nicht verurteilten Angeschuldigten die Kosten zu überbinden, wenn er in zivilrechtlich vorwerfbarer Weise, d.h. im Sinne einer analogen Anwendung der sich aus <ref-law> ergebenden Grundsätze, eine geschriebene oder ungeschriebene Verhaltensnorm klar verletzt und dadurch das Strafverfahren veranlasst oder dessen Durchführung erschwert hat (BGE 120 la 147 E. 3b; 119 la 332 E. 1b; 116 la 162 E. 2c-e; je mit Hinweisen). Dies ist namentlich der Fall, wenn das betreffende Verhalten des Beschuldigten unbestritten oder klar nachgewiesen ist (<ref-ruling> E. 2a in fine).
1.4. Die Vorinstanz stützt die Kostenauflage auf den Sachverhalt, der Gegenstand des eingestellten Strafverfahrens war. Dieser ist aber weder unbestritten, eingestanden noch klar nachgewiesen. Es liegen keine Aussagen des Beschwerdeführers vor, die in die Beweiswürdigung hätten einbezogen werden müssen. Er bestreitet die Anschuldigungen der Ehefrau, welche den Aufzeichnungen des Universitätsspitals zugrunde liegen. Er weist zutreffend darauf hin, dass den Spitalberichten im Hinblick auf die Täterschaft keine weitere Bedeutung als die der Aussagen der Ehefrau zukommt. Zudem legt die Vorinstanz ein darüber hinausgehendes zivilrechtliches Verschulden nicht dar. Indem sie ihren Kostenentscheid auf denselben Sachverhalt stützt, den sie eingestellt hat, legt sie ihre strafrechtliche Missbilligung an den Tag und verletzt damit die Unschuldsvermutung nach <ref-law> und Art. 6 Ziff. 2 EMRK.
Bei diesem Ausgang des Verfahrens kann die Rüge der Verletzung des Anspruchs auf rechtliches Gehör offengelassen werden.
2.
Die Beschwerde ist gutzuheissen, das angefochtene Urteil aufzuheben und die Sache zur neuen Entscheidung an die Vorinstanz zurückzuweisen. Bei diesem Ausgang des Verfahrens hat der Kanton Basel-Stadt den Beschwerdeführer für das bundesgerichtliche Verfahren zu entschädigen (<ref-law>). Insofern wird das Gesuch um unentgeltliche Rechtspflege gegenstandslos. Die Entschädigung ist praxisgemäss dem Rechtsvertreter auszurichten. Es sind keine Gerichtskosten zu erheben (Art. 66 Abs. 1 i.V.m. Abs. 4 BGG).
Mit dem Entscheid in der Sache wird das Gesuch um aufschiebende Wirkung gegenstandslos.

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird gutgeheissen, der Entscheid des Appellationsgerichts des Kantons Basel-Stadt vom 7. Mai 2013 aufgehoben und die Sache zur neuen Entscheidung an die Vorinstanz zurückgewiesen.
2.
Es werden keine Gerichtskosten erhoben.
3.
Der Kanton Basel-Stadt hat den Rechtsvertreter des Beschwerdeführers mit Fr. 3'000.-- zu entschädigen.
4.
Dieses Urteil wird den Parteien und dem Appellationsgericht des Kantons Basel-Stadt, Appellationsgerichtspräsidentin, schriftlich mitgeteilt.
Lausanne, 17. März 2014
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Mathys
Die Gerichtsschreiberin: Kratz-Ulmer