Sachverhalt:
A. Der 1971 geborene A._ war seit 1. Januar 2007 bis zu seiner Kündigung des Arbeitsverhältnisses per 30. September 2009 als Assistance Insurance Broker bei der Firma X._ tätig gewesen. Während einer anschliessenden Urlaubsreise nach Spanien wurde er festgenommen, was zu seiner vom 26. Oktober 2009 bis 15. Dezember 2010 dauernden Inhaftierung in einer spanischen Haftanstalt führte. Nachdem er auf Bewährung freigelassen worden war, konnte er am 15. Juli 2011 wieder in die Schweiz einreisen. Am 18. Juli 2011 meldete er sich zum Leistungsbezug bei der Arbeitslosenversicherung an. Die Öffentliche Arbeitslosenkasse Basel-Stadt verneinte einen Anspruch auf Arbeitslosenentschädigung, da A._ weder die Beitragszeit erfüllt habe, noch von der Erfüllung der Beitragszeit befreit sei (Verfügung vom 26. Juli 2011). Daran hielt die Kasse mit Einspracheentscheid vom 4. Oktober 2011 fest.
B. Die dagegen erhobene Beschwerde wies das Sozialversicherungsgericht des Kantons Basel-Stadt mit Entscheid vom 15. Februar 2012 ab.
C. A._ lässt Beschwerde in öffentlich-rechtlichen Angelegenheiten führen mit dem Begehren um Anerkennung des Anspruchs auf Arbeitslosenentschädigung.
Das Amt für Wirtschaft und Arbeit und das Sozialversicherungsgericht beantragen Abweisung der Beschwerde, während das Staatssekretariat für Wirtschaft (SECO) auf eine Vernehmlassung verzichtet.

Erwägungen:
1. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten (Art. 82 ff. BGG) kann wegen Rechtsverletzung gemäss Art. 95 f. BGG erhoben werden. Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (Art. 105 Abs. 1 BGG), und kann deren Sachverhaltsfeststellung von Amtes wegen nur berichtigen oder ergänzen, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von Art. 95 BGG beruht (Art. 105 Abs. 2 BGG).
2. 2.1 Gemäss Art. 8 Abs. 1 lit. e AVIG hat Anspruch auf Arbeitslosenentschädigung, wer die Beitragszeit erfüllt hat (Art. 13 AVIG) oder von der Erfüllung der Beitragszeit befreit ist (Art. 14 AVIG). Die Beitragszeit hat laut Art. 13 Abs. 1 AVIG erfüllt, wer innerhalb der dafür vorgesehenen Rahmenfrist für die Beitragszeit während mindestens zwölf Monaten eine beitragspflichtige Beschäftigung ausgeübt hat. Von der Erfüllung der Beitragszeit ist gemäss Art. 14 Abs. 1 AVIG u.a. befreit, wer innerhalb der Rahmenfrist während insgesamt mehr als zwölf Monaten wegen Aufenthalt in einer schweizerischen Haft- oder Arbeitserziehungsanstalt oder in einer ähnlichen schweizerischen Einrichtung (lit. c) nicht in einem Arbeitsverhältnis stand und deshalb die Beitragszeit nicht erfüllen konnte. Zwischen der Nichterfüllung der Beitragszeit und dem geltend gemachten Befreiungstatbestand muss ein Kausalzusammenhang vorliegen, wobei das Hindernis während mehr als zwölf Monaten bestanden haben muss (<ref-ruling> E. 1.2 S. 280).
2.2 Die Befreiungstatbestände von Art. 14 Abs. 1 AVIG sind als Ausnahmeklausel grundsätzlich restriktiv auszulegen und im Verhältnis zur Beitragszeit subsidiär. Sie gelangen daher nur zur Anwendung, wenn die in Art. 13 Abs. 1 AVIG verlangte Erfüllung der Mindestbeitragszeit aus den in Art. 14 Abs. 1 AVIG genannten Gründen nicht möglich ist (Thomas Nussbaumer, Arbeitslosenversicherung, in: Soziale Sicherheit, SBVR Bd. XIV, 2007, S. 2248 Rz. 233). Die Beitragszeit hat selbst dann den Vorrang, wenn diese Lösung in bestimmten Einzelfällen (vgl. Höhe des versicherten Verdienstes [Art. 23 AVIG] und Pauschalansätze [Art. 41 AVIV] ungünstiger sein sollte (Gerhard Gerhards, Kommentar zum Arbeitslosenversicherungsgesetz [AVIG], Bd. I, 1987, N. 8 zu Art. 14 AVIG).
3. 3.1 Ausser Frage steht, dass der Versicherte innerhalb der für die Erfüllung der Beitragszeit massgebenden Rahmenfrist vom 18. Juli 2009 bis 17. Juli 2011 nicht während mindestens zwölf Monaten eine beitragspflichtige Beschäftigung ausgeübt hat (Art. 13 Abs. 1 AVIG). Streitig ist einzig, ob er sich durch den Aufenthalt in einer spanischen Haftanstalt auf den Befreiungstatbestand des Art. 14 Abs. 1 lit c AVIG berufen kann.
3.2 De Vorinstanz erwog, angesichts des klaren und eindeutigen Wortlauts der Bestimmung gäbe es keinen Spielraum für eine andere Auslegung. Eine allfällige unechte Gesetzeslücke sei auch nicht mittels richterlicher Rechtsfortbildung zu schliessen, weshalb auf den klaren Wortlaut von Art. 14 Abs. 1 lit. c AVIG abzustellen sei und der Versicherte den angerufenen Befreiungstatbestand nicht erfülle. Art. 14 Abs. 1 lit. c AVIG verstosse überdies nicht gegen das gemeinschafts- bzw. abkommensrechtliche Diskriminierungsverbot im Sinne von Art. 9 Abs. 2 Anhang I FZA.
3.3 Dementgegen stellt sich der Beschwerdeführer letztinstanzlich auf den Standpunkt, es liege ein triftiger Grund vor, um vom klaren Wortlaut des Art. 14 Abs. 1 lit. c AVIG abzuweichen. Die mit der AVIG-Revision per 1. Januar 2003 im Zuge der Umsetzung des Personenfreizügigkeitsabkommens in Kraft gesetzte Bestimmung habe lediglich zum Ziel, Personen, die sich zuvor noch nie in der Schweiz aufgehalten hätten und die nach kurzer Beschäftigungsdauer in der Schweiz einen Arbeitslosenentschädigungsanspruch geltend machten, die Berufung auf den Befreiungstatbestand zu verwehren. Einer solchen Personengruppe gehöre er durch seine persönliche und soziale Verankerung in der Schweiz nicht an.
4. 4.1 Ausgangspunkt jeder Auslegung bildet der Wortlaut der Bestimmung. Ist der Text nicht ganz klar und sind verschiedene Interpretationen möglich, so muss nach seiner wahren Tragweite gesucht werden unter Berücksichtigung aller Auslegungselemente, namentlich des Zwecks, des Sinnes und der dem Text zugrunde liegenden Wertungen. Wichtig ist ebenfalls der Sinn, der einer Norm im Kontext zukommt. Vom klaren, d.h. eindeutigen und unmissverständlichen Wortlaut darf nur abgewichen werden, wenn triftige Gründe dafür vorliegen, dass der Wortlaut nicht den wahren Sinn der Bestimmung wiedergibt. Solche Gründe können sich aus der Entstehungsgeschichte der Bestimmung, aus ihrem Grund und Zweck oder aus dem Zusammenhang mit andern Vorschriften ergeben (<ref-ruling> E. 5.1 S. 94 mit Hinweisen; Urteil [des Bundesgerichts] 9C_101/20212 vom 10. Januar 2012). Bei der Auslegung neuerer Bestimmungen kommt den Gesetzesmaterialien eine besondere Stellung zu, weil veränderte Umstände oder ein gewandeltes Rechtsverständnis eine andere Lösung weniger nahelegen (<ref-ruling> E. 3.1 S. 11; <ref-ruling> E. 2.6 S. 196, für die ZGB-Revision von 1998/2000). Das Bundesgericht hat sich bei der Auslegung von Erlassen stets von einem Methodenpluralismus leiten lassen und nur dann allein auf das grammatische Element abgestellt, wenn sich daraus zweifelsfrei die sachlich richtige Lösung ergab (<ref-ruling> E. 3.1 S. 10; <ref-ruling> E. 2 S. 710).
4. 4.1 Ausgangspunkt jeder Auslegung bildet der Wortlaut der Bestimmung. Ist der Text nicht ganz klar und sind verschiedene Interpretationen möglich, so muss nach seiner wahren Tragweite gesucht werden unter Berücksichtigung aller Auslegungselemente, namentlich des Zwecks, des Sinnes und der dem Text zugrunde liegenden Wertungen. Wichtig ist ebenfalls der Sinn, der einer Norm im Kontext zukommt. Vom klaren, d.h. eindeutigen und unmissverständlichen Wortlaut darf nur abgewichen werden, wenn triftige Gründe dafür vorliegen, dass der Wortlaut nicht den wahren Sinn der Bestimmung wiedergibt. Solche Gründe können sich aus der Entstehungsgeschichte der Bestimmung, aus ihrem Grund und Zweck oder aus dem Zusammenhang mit andern Vorschriften ergeben (<ref-ruling> E. 5.1 S. 94 mit Hinweisen; Urteil [des Bundesgerichts] 9C_101/20212 vom 10. Januar 2012). Bei der Auslegung neuerer Bestimmungen kommt den Gesetzesmaterialien eine besondere Stellung zu, weil veränderte Umstände oder ein gewandeltes Rechtsverständnis eine andere Lösung weniger nahelegen (<ref-ruling> E. 3.1 S. 11; <ref-ruling> E. 2.6 S. 196, für die ZGB-Revision von 1998/2000). Das Bundesgericht hat sich bei der Auslegung von Erlassen stets von einem Methodenpluralismus leiten lassen und nur dann allein auf das grammatische Element abgestellt, wenn sich daraus zweifelsfrei die sachlich richtige Lösung ergab (<ref-ruling> E. 3.1 S. 10; <ref-ruling> E. 2 S. 710).
4.2 4.2.1 Lit. c der Befreiungstatbestände nach Art. 14 Abs. 1 AVIG (vgl. E. 2 hiervor) lautet: "eines Aufenthaltes in einer schweizerischen Haft- oder Arbeitserziehungsanstalt oder in einer ähnlichen schweizerischen Einrichtung." ("séjour dans un établissement suisse de détention ou d'éducation au travail, ou dans une institution suisse de même nature", "soggiorno in un istituto svizzero per l'esecuzione delle pene d'arresto o d'educazione al lavoro o in un istituto svizzero analogo" in der französischen und italienischen Textfassung).
4.2.2 Die Parteien sind sich einig, dass damit ein klarer Gesetzeswortlaut vorliegt. An einen solchen ist die rechtsanwendende Behörde gebunden.
4.3 Nach der Botschaft des Bundesrates vom 23. Juni 1999 zur Genehmigung der sektoriellen Abkommen zwischen der Schweiz und der EG (BBl 1999 S. 6128) soll der Artikel 14 Absatz 1 Buchstabe c nur dann zur Anwendung kommen, wenn sich der Betroffene in der Schweiz in einer Haft- oder ähnlichen Anstalt aufgehalten hat. Personen, die sich vorher noch nie in der Schweiz aufgehalten haben und die im Ausland eine Haftstrafe verbüssten, sollen sich nicht nach einer kurzfristigen Beschäftigung in der Schweiz auf diesen Befreiungstatbestand berufen können (S. 6364). Sowohl in den Kommissionen als auch in den Plenumsberatungen der Eidgenössischen Kammern wurde dem Entwurf des Bundesrates diskussionslos zugestimmt (Protokoll der nationalrätlichen Spezialkommission Personenverkehr vom 10.-11. Mai 1999, S. 47 f.; Protokoll der aussenpolitischen Kommission des Ständerates vom 20.-21. Mai 1999, S. 15 f.; Amtliches Bulletin der Bundesversammlung, NR vom 2. September 1999 S. 15099 ff. und SR vom 31. August 1999 S. 657 f.).
Die Inlandverknüpfung in Art. 14 AVIG wurde mit der Absicht eingeführt, Angehörigen der EU- und EFTA-Staaten den Zugang zum Versicherungssystem zu erschweren (BBl 1999 S. 6364-6366). Aus der Entstehungsgeschichte und den in den Materialien klar geäusserten Beweggründen (vgl. Nussbaumer, a.a.O., S. 2257 Rz. 257) muss geschlossen werden, dass der Bundesrat den Befreiungstatbestand von Art. 14 Abs. 1 lit. c AVIG ohne Ausnahme mit dem Aufenthalt in einer schweizerischen Haft- oder Arbeitserziehungsanstalt (oder einer ähnlichen Einrichtung) verknüpfen wollte. Er wollte damit - dem Sinn und Zweck der in Art. 14 Abs. 1 lit. c AVIG vorgenommenen Inlandverknüpfung entsprechend - der Gefahr begegnen, dass ein Personenkreis ohne engere soziale und berufliche Bindung an die Schweiz vom Versicherungssystem profitieren könnte. Zur Vermeidung von Abgrenzungsschwierigkeiten legte man Wert auf die Schaffung klarer Voraussetzungen für die Befreiung von der Erfüllung der Beitragszeit, was mit der vorliegenden Formulierung gegeben ist. Ob der gewählte Wortlaut ein geeignetes Mittel ist, um einen tatsächlichen Bezug zum schweizerischen Arbeitsmarkt herzustellen (vgl. Patricia Usinger-Egger, Ausgewählte Rechtsfragen des Arbeitslosenversicherungsrechts im Verhältnis Schweiz-EU, in: Thomas Gächter [Hrsg.], Das Europäische Koordinationsrecht der sozialen Sicherheit und die Schweiz. Erfahrungen und Perspektiven, 2006, S. 53) ist eine sozialpolitische Frage, die primär vom Gesetzgeber zu beantworten ist.
4.4 Aus dem Gesagten ergibt sich, dass die Materialen mit Blick auf die Ausführungen in der Botschaft den klaren Wortlaut der Gesetzesbestimmung stützen. Aus den Darlegungen in der Botschaft geht somit nicht hervor, dass nach dem Willen des Gesetzgebers abweichend vom klaren Gesetzeswortlaut Ausnahmen von der absolut formulierten Voraussetzung des Aufenthalts in einer schweizerischen Haft- oder Arbeitserziehungsanstalt oder in einer ähnlichen schweizerischen Einrichtung möglich sein sollen. Hätte der Gesetzgeber den Anwendungsbereich auf den Aufenthalt in einer entsprechenden Einrichtung im Ausland ausdehnen wollen, hätte er dies im Wortlaut der Bestimmung zum Ausdruck gebracht. Es bestehen keine triftigen Gründe, vom unmissverständlichen Wortlaut abzuweichen. Soweit dieses Ergebnis sachlich unbefriedigend ist, liegt allenfalls eine unechte Gesetzeslücke vor, deren Korrektur den rechtsanwendenden Organen grundsätzlich nicht oder nur unter strengen - hier nicht gegebenen - Voraussetzungen erlaubt ist (<ref-ruling> E. 4b/cc S. 41 mit Hinweisen; <ref-ruling> S. 164f. E. 4c).
4.5 Letztinstanzlich zu Recht nicht mehr geltend gemacht wird eine Verletzung des Gleichbehandlungsgebots betreffend soziale Vergünstigungen im Sinne des Art. 7 Abs. 2 der Verordnung Nr. 1612/68 und, als Ausfluss davon, des Art. 9 Abs. 2 von Anhang I zum Abkommen vom 21. Juni 1999 zwischen der Schweizerischen Eidgenossenschaft einerseits und der Europäischen Gemeinschaft und ihren Mitgliedstaaten andererseits über die Freizügigkeit (FZA; SR 0.142.112.681; vgl. <ref-ruling>). Selbst wenn der persönliche Geltungsbereich des FZA sowie der Verordnungen, auf die das Abkommen verweist, aufgrund der italienischen Staatsbürgerschaft des Beschwerdeführers grundsätzlich zu bejahen wäre, liegt weder eine direkte noch indirekte Diskriminierung vor. Es wird auf die diesbezüglichen Erwägungen der Vorinstanz verwiesen. Der angefochtene Entscheid ist somit rechtens.
5. Dem Verfahrensausgang entsprechend sind die Gerichtskosten vom Beschwerdeführer als unterliegender Partei zu tragen (Art. 66 Abs. 1 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen.
2. Die Gerichtskosten von Fr. 500.- werden dem Beschwerdeführer auferlegt.
3. Dieses Urteil wird den Parteien, dem Sozialversicherungsgericht des Kantons Basel-Stadt und dem Staatssekretariat für Wirtschaft (SECO) schriftlich mitgeteilt.
Luzern, 21. Februar 2013
Im Namen der I. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Das präsidierende Mitglied: Ursprung
Die Gerichtsschreiberin: Polla