Sachverhalt:
A. Das Strafgericht des Kantons Basel-Stadt befand X._ am 18. Januar 2011 des Mordes, der einfachen Körperverletzung und der Nötigung schuldig. Es verurteilte ihn zu einer Freiheitsstrafe von 15 Jahren. Gegen dieses Urteil erhoben die Staatsanwaltschaft des Kantons Basel-Stadt und X._ Berufung.
B. Das Appellationsgericht des Kantons Basel-Stadt sprach X._ am 4. September 2012 des Mordes und der Nötigung schuldig. Vom Vorwurf der einfachen Körperverletzung sprach es ihn frei. Es verurteilte ihn zu einer Freiheitsstrafe von 14 3⁄4 Jahren und bestätigte im Übrigen das erstinstanzliche Urteil.
Das Appellationsgericht geht beim Tötungsdelikt von folgendem Sachverhalt aus:
Die Liebesbeziehung zwischen X._ und D.Y._ war seit geraumer Zeit von gegenseitiger Eifersucht geprägt. Es kam wiederholt zu Streit. D.Y._ störte es, dass ihr Geliebter mit seiner Ehefrau zusammenlebte und ihrer Vorstellung nach mit dieser auch intim verkehrte. Daher wollte sie ihn zeitweise nicht mehr sehen und ihre Beziehung beenden. Sie kontaktierte ihren Liebhaber und wollte ihn mit der Behauptung eifersüchtig machen, sie habe eine anderweitige sexuelle Beziehung. X._ suchte in der Nacht vom 23./24. Oktober 2010 D.Y._ in deren Wohnung auf. Da beschuldigte sie ihn erneut, mit seiner Ehefrau sexuellen Verkehr gehabt zu haben. Nachdem sie wiederholt erklärte, sie habe ihn auch betrogen, holte X._ ein Messer, um die Wahrheit herauszufinden. Obwohl er seine Geliebte damit bedrohte, blieb sie bei der Behauptung eines anderweitigen sexuellen Kontakts. Der von X._ in den Hals seiner Liebhaberin geführte Messerstich durchtrennte deren Hauptschlagader. Neben dieser zum Tod führenden Verletzung befand sich in ihrer Lendengegend eine weitere tiefe Stichwunde.
C. X._ führt Beschwerde in Strafsachen und beantragt, das Urteil des Appellationsgerichts sei teilweise aufzuheben. Er sei vom Vorwurf des Mordes freizusprechen. Stattdessen sei er der (eventual-)vorsätzlichen Tötung schuldig zu befinden und zu einer Freiheitsstrafe von maximal acht Jahren zu verurteilen. Eventualiter sei die Sache zur neuen Entscheidung an die Vorinstanz zurückzuweisen. Zudem stellt er das Gesuch um unentgeltliche Rechtspflege und Verbeiständung.

Erwägungen:
1. 1.1 Der Beschwerdeführer wendet sich gegen die rechtliche Würdigung der Tötung. Mangels besonderer Skrupellosigkeit liege kein Mord vor. Sein Handeln sei das Ergebnis einer jahrelangen Konfliktsituation, die teilweise durch das Opfer heraufbeschworen worden sei und unter der beide stark gelitten hätten. Die Schlussfolgerung der Vorinstanz, er habe seine Geliebte aus egoistischen Motiven getötet - er sei eifersüchtig und wütend gewesen - sei nicht haltbar. Er habe sie zuvor lange mit ihrem Ehemann "teilen" müssen. Es sei nicht ersichtlich, inwiefern er egoistisch gehandelt habe, indem er "seine Liebste" getötet habe. Vielmehr habe er sich in einer heftigen Gemütsbewegung befunden, als er das Opfer in den Hals gestochen habe. Die Vorinstanz stelle den Sachverhalt unrichtig fest, da sie willkürlich Tatmotive hinein interpretiere. Im Lichte aller Umstände - namentlich der Tatausführung sowie des Nachtatverhaltens - und insbesondere, dass das Tatmotiv nicht klar sei und ein Tatentschluss fehle, sei "in dubio pro reo" anzunehmen, er habe den Tod seiner Geliebten lediglich eventualvorsätzlich in Kauf genommen.
1.2 Die Vorinstanz erwägt unter Verweis auf die erste Instanz, der Beschwerdeführer habe aus der Küche ein Messer geholt, um seine Geliebte damit zu bedrohen. Da sie sich nicht zur gewünschten Aussage habe nötigen lassen, habe er seine Drohung in die Tat umgesetzt. Er habe somit nicht im Affekt zu einem Messer gegriffen, das zufällig in der Nähe gewesen sei. Auch wenn nicht erstellt sei, dass die Trennungsabsichten der Geliebten unwiderruflich gewesen seien, habe das mögliche Ende der Beziehung bereits seit einiger Zeit im Raum gestanden und den Beschwerdeführer in der Tatnacht nicht unvorbereitet getroffen. Auch den angeblich neuen Freund der Liebhaberin habe diese schon früher erwähnt. Gemäss forensisch-psychiatrischem Gutachten fehlten mehrere entscheidende Merkmale eines Affektdelikts (kein charakteristischer Affektaufbau und -abbau, keine schwere Erschütterung unmittelbar nach der Tat, keine Störung der Sinn- und Erlebniskontinuität und keine Einengung des Wahrnehmungsfelds sowie der seelischen Abläufe) (Urteil S. 4 f. E. 3.1; erstinstanzliches Urteil S. 24 E. 3.4.2; Gutachten kantonale Akten S. 1741/33). Die Vorinstanz führt weiter aus, auch das Nachtatverhalten des Beschwerdeführers spreche gegen ein Handeln im Affekt. So habe er den Tatort nach der tödlichen Verletzung entgegen seinen Behauptungen nicht fluchtartig verlassen, sondern dem Opfer einen weiteren tiefen Stich beigebracht und sich danach um die Beseitigung der Spuren bemüht. Es bestünden ferner keine Hinweise, dass er unter einer grossen seelischen Belastung gestanden habe. Insgesamt sei keine Ausnahmesituation zu erkennen, die den Entschluss zur Tat als menschlich begreiflich oder einfühlbar erscheinen lasse (Urteil S. 5 E. 3.1).
Die Vorinstanz hält fest, gemäss Angaben des Beschwerdeführers habe er seiner Geliebten im Zusammenhang mit ihrer Behauptung, intim mit einem anderen Mann verkehrt zu sein, das Messer in den Hals gestochen. Wenn er sie wegen dieser Mitteilung getötet habe, d.h. aus Eifersucht und Wut aufgrund ihrer Untreue, so liege hierin ein offensichtlich egoistisches Motiv. Dies gelte auch, wenn er eine Trennung hätte befürchten müssen, da er ihr diesfalls die Berechtigung abgesprochen hätte, ohne ihn weiterzuleben. Die Beziehung sei zwar gegen Ende durch gegenseitige Eifersucht belastet gewesen. Gleichwohl hätten diesbezüglich weder aussergewöhnliche noch überraschende Umstände vorgelegen. Zudem habe der Beschwerdeführer nicht geglaubt, dass seine Geliebte ihn mit einem anderen Mann betrogen habe. Wenn er an ihre Treue geglaubt habe, sei er nur darüber verärgert gewesen, dass sie nicht gesagt habe, was er habe hören wollen, d.h. dass sie ihn nicht ernst genommen habe und er in dieser Hinsicht keine Kontrolle und Macht über sie habe ausüben können. Für diese Motivation spreche der Umstand, dass er sie mit dem Messer bedroht habe, bloss weil ihm ihre Äusserung nicht gepasst habe. Dabei bezeichne er sein Vorgehen als "normal" bzw. "Spass". Er habe die Wahrheit "rausholen" wollen. Insofern liege ein noch krasseres Missverhältnis zwischen den vom Beschwerdeführer verfolgten Interessen und der Auslöschung des Lebens seiner Geliebten vor, welches die Tat erst recht als besonders skrupellos erscheinen lasse (Urteil S. 7 f. E. 3.2.4).
1.3 Soweit sich der Beschwerdeführer gegen die vorinstanzliche Sachverhaltsfeststellung wendet, setzt er sich darüber hinweg, ergänzt sie und nimmt eine eigene Beweiswürdigung vor, ohne dass sich aus seinen Ausführungen ergäbe, dass und inwiefern die Beweiswürdigung der Vorinstanz willkürlich und ihre tatsächlichen Feststellungen offensichtlich unrichtig wären. Auf die Beschwerde ist insoweit nicht einzutreten. Die Sachverhaltsfeststellung der Vorinstanz kann vor Bundesgericht nur gerügt werden, wenn sie willkürlich ist (<ref-law>; <ref-ruling> E. 4.2.3 S. 5; <ref-ruling> E. 1.4.1; zu den Begründungsanforderungen <ref-law> sowie <ref-ruling> E. 1.4.1 mit Hinweisen).
1.4 Eine vorsätzliche Tötung ist als Mord zu qualifizieren, wenn der Täter besonders skrupellos handelt, namentlich wenn sein Beweggrund, der Zweck der Tat oder die Art der Ausführung besonders verwerflich sind (<ref-law>). Mord zeichnet sich nach der Rechtsprechung durch eine aussergewöhnlich krasse Missachtung fremden Lebens bei der Durchsetzung eigener Absichten aus. Es geht um die besonders verwerfliche Auslöschung eines Menschenlebens. Für die Qualifikation verweist das Gesetz in nicht abschliessender Aufzählung auf äussere (Ausführung) und innere Merkmale (Beweggrund, Zweck). Diese müssen nicht alle erfüllt sein, um Mord anzunehmen. Entscheidend ist eine Gesamtwürdigung der äusseren und inneren Umstände der Tat. Eine besondere Skrupellosigkeit kann beispielsweise entfallen, wenn das Tatmotiv einfühlbar und nicht krass egoistisch war, so etwa wenn die Tat durch eine schwere Konfliktsituation ausgelöst wurde. Für Mord typische Fälle sind die Tötung eines Menschen zum Zwecke des Raubes, Tötungen aus religiösem oder politischem Fanatismus oder aus Geringschätzung. Die für eine Mordqualifikation konstitutiven Elemente sind jene der Tat selber, während Vorleben und Verhalten nach der Tat nur heranzuziehen sind, soweit sie tatbezogen sind und ein Bild der Täterpersönlichkeit geben (<ref-ruling> E. 1a mit Hinweisen).
1.5 Der Beschwerdeführer macht geltend, er habe den Tod seiner Geliebten lediglich in Kauf genommen (Beschwerde S. 8 N. 16).
1.5.1 Vorsätzlich begeht ein Verbrechen oder Vergehen, wer die Tat mit Wissen und Willen ausführt. Vorsätzlich handelt bereits, wer die Verwirklichung der Tat für möglich hält und in Kauf nimmt (Art. 12 Abs. 2). Das Bundesgericht hat wiederholt dargelegt, wann Eventualvorsatz gegeben ist (<ref-ruling> E. 4.2.3 S. 4 mit Hinweis).
1.5.2 Die Vorinstanz verletzt kein Bundesrecht, indem sie annimmt, angesichts der Tatausführung habe der Beschwerdeführer direkt vorsätzlich gehandelt. Sie erwägt zutreffend, ein von der Seite gegen die Halsmitte bis zur Wirbelsäule beigebrachter Messerstich (ca. 1.5 cm breit und 5-6 cm lang) könne nur bedeuten, dass der Täter den Tod des Opfers beabsichtigt habe. Bei einem solchen Vorgehen sei der Tod nicht nur wahrscheinlich, sondern sicher (Urteil S. 4 E. 3). Entgegen der Auffassung des Beschwerdeführers kann im Übrigen auch ein Mord eventualvorsätzlich begangen werden (<ref-ruling> E. 3b; Urteil 6B_232/2012 vom 8. März 2013 E. 1.4.2 mit Hinweisen).
1.6 Angesichts der von der Vorinstanz schlüssig dargelegten möglichen Tatmotive und der Ausführung der Tat bestehen an der besonderen Skrupellosigkeit des Handelns des Beschwerdeführers keine Zweifel. Die in Frage kommenden Beweggründe, (a) Eifersucht und Wut wegen der Untreue seiner Geliebten, (b) ihr ein vom Beschwerdeführer getrennt geführtes Leben zu verunmöglichen oder (c) den Ärger darüber, dass sie sich trotz der Bedrohung mit dem Messer nicht entsprechend seinen Wünschen äusserte, sind vorliegend besonders verwerflich. Selbst die vom Beschwerdeführer dargelegten Umstände lassen keines dieser Tatmotive als einfühlbar oder als Ausdruck einer schweren Konfliktsituation erscheinen, sondern als krass egoistischen Akt. Indizien für die besondere Skrupellosigkeit ergeben sich auch aus der Ausführung der Tat, indem der Beschwerdeführer zielstrebig und kaltblütig mit einem Messerstich die Halsschlagader durchtrennte. Der Umstand, die Tat ohne Rücksicht darauf ausgeführt zu haben, dass der Sohn des Opfers im Zimmer daneben schlief und er den Jungen nach der Tötung alleine in der Wohnung zurückliess mit der naheliegenden Möglichkeit, dass dieser die blutüberströmte Leiche auffinden würde, wie es dann auch der Fall war (Anklageschrift vom 10. September 2010, erstinstanzliches Urteil S. 12), offenbart eine besondere Gefühlskälte. Die Tat zeichnet sich durch eine aussergewöhnlich krasse Missachtung fremden Lebens bei der Durchsetzung eigener Absichten aus. Die Verurteilung des Beschwerdeführers wegen Mordes verletzt kein Bundesrecht.
2. Die Beschwerde ist abzuweisen, soweit darauf eingetreten werden kann. Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung ist infolge Aussichtslosigkeit der Beschwerde abzuweisen (Art. 64 Abs. 1 und 2 BGG). Der finanziellen Lage des Beschwerdeführers ist bei der Festsetzung der Gerichtskosten Rechnung zu tragen (Beschwerde S. 9; <ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung wird abgewiesen.
3. Die Gerichtskosten von Fr. 800.-- werden dem Beschwerdeführer auferlegt.
4. Dieses Urteil wird den Parteien und dem Appellationsgericht des Kantons Basel-Stadt schriftlich mitgeteilt.
Lausanne, 13. Mai 2013
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Mathys
Die Gerichtsschreiberin: Pasquini