Sachverhalt: A. Der 1972 geborene A._ ist indischer Staatsangehöriger und war ab Mai 2012 bis 31. Oktober 2017 als doktorierender Assistent an der Universität B._ angestellt. Er schloss seine Ausbildung am 11. Januar 2018 mit dem Doktortitel PhD ab. Seine auf "Ausbildung und Erwerb" lautende Aufenthaltsbewilligung "B" war bis Ende Februar 2018 gültig. A._ meldete sich am 2. Oktober 2017 zum Leistungsbezug bei der Arbeitslosenversicherung ab 1. November 2017 an. Mit Verfügung vom 13. Oktober 2017 verneinte die Öffentliche Arbeitslosenkasse Basel-Stadt den Anspruch auf Arbeitslosenentschädigung, da A._ über keine Aufenthaltsbewilligung verfüge, die ihm die Aufnahme einer neuen Erwerbstätigkeit in der Schweiz erlaube, weshalb er nicht vermittlungsfähig sei. Daran hielt sie mit Einspracheentscheid vom 16. November 2017 fest. B. Die dagegen geführte Beschwerde wies das Sozialversicherungsgericht des Kantons Basel-Stadt mit Entscheid vom 12. März 2018 ab. C. A._ lässt Beschwerde in öffentlich-rechtlichen Angelegenheiten führen und beantragen, in Anerkennung seiner Vermittlungsfähigkeit sei der vorinstanzliche Entscheid aufzuheben und es sei ihm Arbeitslosenentschädigung zuzusprechen. Eventualiter sei die Sache zur Neubeurteilung an die Arbeitslosenkasse zurückzuweisen. Weiter ersucht er um unentgeltliche Rechtspflege. Die Arbeitslosenkasse verzichtet ebenso auf eine Vernehmlassung wie das Staatssekretariat für Wirtschaft (SECO). Die Vorinstanz nimmt zu den Anträgen und Vorbringen von A._ ablehnend Stellung.