Sachverhalt: A. Das Appellationsgericht des Kantons Basel-Stadt sprach den am 10. März 1982 geborenen X._ am 12. Januar 2007 im Berufungsverfahren des qualifizierten Raubes, der Gefährdung des Lebens, der einfachen Körperverletzung mit einem gefährlichen Gegenstand, der versuchten einfachen Körperverletzung mit einem gefährlichen Gegenstand, der Nötigung, der versuchten Nötigung, der mehrfachen Hehlerei, der Widerhandlung gegen das Betäubungsmittelgesetz, der einfachen und groben Verletzung von Verkehrsregeln sowie der mehrfachen Widerhandlung gegen das Waffengesetz schuldig. Es verurteilte ihn zu einer Freiheitsstrafe von 8 Jahren. Gleichzeitig widerrief es den bedingten Aufschub des Vollzugs einer vom Strafgericht des Kantons Basel-Stadt am 2. Mai 2001 ausgesprochenen Gefängnisstrafe von 12 Monaten (wegen mehrfachen, teilweise versuchten Raubes und versuchter Nötigung). Die von X._ dagegen erhobene Beschwerde (Schuldpunkt, Strafzumessung) wies das Bundesgericht am 12. Mai 2007 ab (Verfahren 6B_48/2007). B. X._ verbüsste seine Strafe in der Strafanstalt Bostadel. Er ersuchte am 4. Juli 2007 um Vollzugslockerungen. Die Interkantonale Fachkommission zur Beurteilung der Gemeingefährlichkeit von Straftätern der Kantone Solothurn, Basel-Landschaft und Basel-Stadt (IFKGS) stufte ihn am 29. Oktober 2007 als gemeingefährlich ein. Hinweise auf eine Krankheit oder eine Persönlichkeitsstörung schloss die IFKGS aus. Das Justiz- und Sicherheitsdepartement (JSD) des Kantons Basel-Stadt gab auf Empfehlung der IFKGS ein Gutachten beim Forensisch-Psychiatrischen Dienst (FPD) der Universität Bern in Auftrag. Gemäss Gutachten vom 24. September 2008 leidet X._ an einer schwer zu behandelnden paranoiden und narzisstischen Persönlichkeitsstörung, welche bereits im Tatzeitpunkt bestanden hat. Die von ihm ausgehende Rückfallgefahr wurde als erheblich und die Legalprognose insgesamt als sehr ungünstig eingestuft. Es seien mit hoher Wahrscheinlichkeit namentlich Raubstraftaten zu erwarten, wobei es zu Gewalttaten gegenüber den Opfern kommen könne, wenn sich diese wehrten. Dass es insofern auch zu einer Tötung kommen könnte, sei nicht ausgeschlossen. Es sei jedoch nicht davon auszugehen. Am 10. November 2008 stufte die IFKGS X._ erneut als gemeingefährlich ein. Am 30. Dezember 2008 stellte das JSD dem Appellationsgericht den Antrag auf Prüfung der nachträglichen Anordnung einer vollzugsbegleitenden psychotherapeutischen ambulanten Behandlung. Das Appellationsgericht des Kantons Basel-Stadt wies diesen Antrag am 4. Dezember 2009 ab. Für die nachträgliche Anordnung einer ambulanten Behandlung bestünde keine gesetzliche Grundlage. Es warf die Frage auf, ob nicht allenfalls eine stationäre Behandlung im Sinne von Art. 65 Abs. 1 StGB in Betracht zu ziehen wäre, und regte für diesen Fall die Einholung eines Ergänzungsgutachtens an. Namentlich gestützt auf das beim FPD der Universität Bern eingeholte Ergänzungsgutachten vom 30. Juni 2010 beantragte das JSD am 7. Juli 2010 die Prüfung der nachträglichen Anordnung einer Verwahrung gemäss Art. 65 Abs. 2 StGB, wobei auch die Möglichkeit der nachträglichen Anordnung einer stationären Massnahme nach Art. 65 Abs. 1 StGB nicht ausgeschlossen werden sollte. Das Appellationsgericht des Kantons Basel-Stadt ordnete am 6. Mai 2011 über X._ nachträglich eine Verwahrung im Sinne von Art. 65 Abs. 2 StGB an. C. Das Bundesgericht hiess die von X._ dagegen erhobene Beschwerde mit Urteil vom 30. Januar 2012 teilweise gut und wies die Angelegenheit an die Vorinstanz zurück. Es bejahte die Revisionsvoraussetzungen, hielt aber die Anordnung der Verwahrung gemäss Art. 64 StGB i.V.m. Art. 65 Abs. 2 StGB für bundesrechtswidrig. Es sei zu prüfen, ob eine stationäre therapeutische Massnahme im Sinne von Art. 59 StGB i.V.m. Art. 65 Abs. 1 StGB anzuordnen sei (6B_487/2011). Am 22. August 2012 ordnete das Appellationsgericht des Kantons Basel-Stadt über X._ eine stationäre therapeutische Massnahme im Sinne von Art. 59 StGB i.V.m. Art. 65 Abs. 1 StGB an. D. X._ führt Beschwerde in Strafsachen. Er beantragt, es sei festzustellen, dass das Appellationsgericht für die nachträgliche Anordnung einer stationären Massnahme nach Art. 65 Abs. 1 StGB nicht zuständig sei. Das Verfahren sei dem erstinstanzlichen Strafgericht des Kantons Basel-Stadt zu überweisen. Eventualiter sei der Entscheid vom 22. August 2012 aufzuheben und festzustellen, dass die Voraussetzungen von Art. 65 Abs. 1 StGB nicht gegeben seien und er nach Verbüssung der Strafe aus dem Vollzug zu entlassen sei. X._ ersucht um unentgeltliche Rechtspflege und Verbeiständung. E. Das Appellationsgericht des Kantons Basel-Stadt beantragt gestützt auf die Begründung seines Entscheids vom 22. August 2012 die Abweisung der Beschwerde. Das JSD hat auf eine Stellungnahme zur Beschwerde verzichtet. 