Sachverhalt: A. A.a. Am 2. Februar 2013 entwendete eine unbekannte Täterschaft in zwei Supermärkten im Kanton St. Gallen die Portemonnaies von A._ und B._ und bezog an Geldautomaten insgesamt Fr. 4'500.--. Weitere Versuche, mit einer Mastercard zweimal Fr. 1'000.-- und einmal Fr. 3'000.-- abzuheben, blieben erfolglos. A.b. Die Auswertung des bei den Geldbezügen aufgezeichneten Bildmaterials ergab, dass es sich um denselben Täter handelte. Die Kantonspolizei St. Gallen verbreitete die Bilder per nationalem Fahndungsersuchen. Rückmeldungen kantonaler Polizeikorps ergaben, dass der Täter weiterer Delikte gleichen Schemas verdächtigt wurde. Am 28. März 2013 ersuchte das Untersuchungsamt Gossau die Staatsanwaltschaft des Kantons Solothurn um Verfahrensübernahme mit dem Hinweis, dass es sich gemäss Mitteilung der Kriminalpolizei Schaffhausen vom 22. Februar 2013 bei der Täterschaft um X._ handle. Die Staatsanwaltschaft des Kantons Solothurn verzichtete nach Aktenstudium auf die Eröffnung einer Strafuntersuchung gegen X._. Aufgrund der zur Verfügung stehenden Fotos könne festgehalten werden, dass der Täter vom 2. Februar 2013 dieselbe Person sei, gegen die im Kanton Solothurn bereits ermittelt werde. Dass es sich hierbei um X._ handle, werde stark angezweifelt. Weder die Lippen- und Nasenform noch die Augenbrauenpartie stimmten mit dem Täter überein. Einzig gestützt auf das Foto dränge sich kein Anfangsverdacht gegen X._ auf. Bei gegenteiliger Auffassung sei die für Gerichtsstände zuständige stellvertretende Oberstaatsanwältin zu kontaktieren. A.c. Das Untersuchungsamt Gossau ersuchte am 17. April und 2. Juli 2013 die Staatsanwaltschaft des Kantons Zürich um rechtshilfeweise Befragung von X._. Am 12. Juli 2013 ordnete sie auf Antrag der Kantonspolizei Zürich eine Hausdurchsuchung an dessen Wohnort an, die am frühen Morgen des 16. Juli 2013 stattfand. Gleichentags wurde X._ polizeilich einvernommen. Er konnte anhand seines Passes nachweisen, dass er zur Tatzeit in Brasilien war. A.d. Am 8. August 2013 stellte die Staatsanwaltschaft des Kantons St. Gallen das Strafverfahren gegen X._ ein und wies das von ihm gestellte Genugtuungsbegehren von Fr. 1'000.-- ab. B. Die hiergegen erhobene Beschwerde wies die Anklagekammer des Kantons St. Gallen am 18. September 2013 ab. C. X._ führt Beschwerde in Strafsachen und beantragt, der Entscheid der Anklagekammer sei aufzuheben, und ihm sei eine angemessene Genugtuung auszurichten. Eventuell sei die Sache an die Vorinstanz zurückzuweisen. Subeventuell seien im Fall der Beschwerdeabweisung die vorinstanzlichen Kosten angemessen zu reduzieren. X._ ersucht um aufschiebende Wirkung seiner Beschwerde. D. Die Staatsanwaltschaft des Kantons St. Gallen beantragt, das Gesuch um aufschiebende Wirkung und die Beschwerde abzuweisen. Sie macht für das Beschwerdeverfahren vor Bundesgericht eine Gebühr von Fr. 500.-- geltend. Die Anklagekammer erhebt keine Einwände gegen das Gesuch um aufschiebende Wirkung. Auf eine Vernehmlassung zur Beschwerde hat sie verzichtet. E. Am 12. November 2013 erteilte das präsidierende Mitglied der strafrechtlichen Abteilung der Beschwerde aufschiebende Wirkung.