Sachverhalt: A. A.a Am 15. Juni 1992 überkletterten A._ und B._ den Grenzzaun, um von Konstanz (Deutschland) nach Kreuzlingen zu gelangen. Sie führten sechs Kilogramm Heroin mit sich. Die schweizerische Grenzwache nahm die beiden fest. Im Laufe des Ermittlungsverfahrens stellte sich heraus, dass die Verhafteten nach der Einreise X._ und C._ im Restaurant D._ treffen wollten, um mit deren Hilfe die Drogen nach Rorschach weiterzutransportieren und an Dritte zu übergeben. A.b Die Staatsanwaltschaft des Kantons Thurgau klagte X._ am 29. März 1993 wegen qualifizierter Widerhandlung gegen das Betäubungsmittelgesetz an und beantragte eine Zuchthausstrafe von vier Jahren. A.c Das Bezirksgericht Kreuzlingen lud X._ am 26. April 1993 zur Hauptverhandlung vom 21. Juni 1993 vor. Wenige Tage später ersuchte der amtliche Verteidiger um freies Geleit für X._. Das Bezirksgericht Kreuzlingen bewilligte dieses Gesuch am 6. Mai 1993. X._ reiste am 7. Mai 1993 aus der Schweiz aus, nachdem sein Asylgesuch definitiv abgelehnt worden war. Er blieb der Hauptverhandlung vom 21. Juni 1993 fern. A.d Das Bezirksgericht Kreuzlingen verurteilte X._ am 21. Juni 1993 im Abwesenheitsverfahren wegen qualifizierter Widerhandlung gegen das Betäubungsmittelgesetz zu fünf Jahren Zuchthaus, unter Anrechnung der Untersuchungshaft von 70 Tagen. Dieses Urteil erwuchs unangefochten in Rechtskraft. A.e Am 10. Oktober 2011 wurde X._ bei seiner Einreise in die Schweiz verhaftet und dem Strafvollzug zugeführt. B. X._ beantragte am 19. Oktober 2011, das Strafverfahren sei neu zu beurteilen, und es sei festzustellen, dass die Verfolgungsverjährung eingetreten sei. Die Berufungsfrist sei wiederherzustellen. Das Bezirksgericht Kreuzlingen wies das Gesuch mit Beschluss vom 30. Dezember 2011 ab. Das Obergericht des Kantons Thurgau lehnte die dagegen gerichtete Beschwerde am 9. Februar 2012 ab, soweit auf sie einzutreten war. C. X._ erhebt gegen das Urteil des Obergerichts Beschwerde in Strafsachen. Er beantragt, das angefochtene Urteil sei aufzuheben. Das Bezirksgericht Kreuzlingen sei anzuweisen, das Urteil vom 21. Juni 1993 aufzuheben, das Verfahren wieder aufzunehmen, die Verjährung zu prüfen und festzustellen, dass diese eingetreten sei. Eventualiter sei die Frist zur Anmeldung der Berufung gegen das Urteil des Bezirksgerichts Kreuzlingen vom 21. Juni 1993 wiederherzustellen, und es sei festzustellen, dass diese gewahrt worden sei, unter Kosten- und Entschädigungsfolgen zulasten der Vorinstanz. Es sei ihm die unentgeltliche Rechtspflege und Verbeiständung zu bewilligen. D. Das Gesuch von X._ um aufschiebende Wirkung bzw. um Haftentlassung wurde mit Präsidialverfügung vom 17. April 2012 abgewiesen. E. Das Obergericht und die Staatsanwaltschaft beantragen die Abweisung der Beschwerde. F. Das Bundesgericht hat den Entscheid öffentlich beraten.