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. 