Sachverhalt: A. X._ wird in der Anklageschrift vom 2. Juni 2014 gewerbsmässiger Betrug zum Nachteil des Amtes für Sozialbeiträge Basel-Stadt zur Last gelegt. Er habe in seinem Antrag auf finanzielle Unterstützung vom 11. Juni 2003 das Amt in der Absicht unrechtmässiger Bereicherung arglistig getäuscht, indem er gegenüber der Mitarbeiterin des Amtes, welche das von ihm unterzeichnete Antragsformular ausgefüllt habe, den Bezug einer Pensionskassenrente der SBB und das Konto bei der UBS, auf welches diese Rente überwiesen worden sei, verschwiegen habe. Zudem habe er im Verlauf der Unterstützung gegenüber dem Amt verschwiegen, dass die (am 11. Juni 2003 deklarierte) SUVA-Rente zweimal, nämlich per 1. Juli 2005 und per 1. Januar 2008, erhöht worden sei. Aufgrund dieser Täuschungen habe X._ zwischen August 2002 und Oktober 2008 zu Unrecht zum Schaden des Amtes Ergänzungsleistungen, Prämienverbilligungen und Beihilfen im Betrag von insgesamt CHF 158'544.30 erhalten. B. Bereits mit Verfügungen vom 23. Februar und 2. Juli 2009 sowie Einspracheentscheid vom 30. September 2009 war X._ vom Amt für Sozialbeiträge zur Rückerstattung unrechtmässig bezogener Ergänzungsleistungen, kantonaler Beihilfen, Prämienverbilligungen und Vergütungen von Krankheitskosten im Gesamtbetrag von CHF 158'440.30 verpflichtet worden. Die dagegen erhobenen Beschwerden hatten das Sozialversicherungsgericht Basel-Stadt mit Entscheid vom 20. Dezember 2010 und in der Folge das Bundesgericht mit Urteil 9C_131/2011 vom 19. Dezember 2011 (BGE 138 V 74) abgewiesen. C. C.a. Das Strafgericht des Kantons Basel-Stadt sprach X._ am 25. August 2014 des gewerbsmässigen Betrugs (Art. 146 Abs. 2 StGB) schuldig und verurteilte ihn zu einer Freiheitsstrafe von 15 Monaten, bedingt vollziehbar bei einer Probezeit von 2 Jahren. Bereits mit Entscheid vom 20. November 2013 hatte das Strafgericht des Kantons Basel-Stadt X._ wegen mehrfacher Verletzung der Verkehrsregeln, grober Verletzung der Verkehrsregeln und mehrfachen Fahrens in fahrunfähigem Zustand zu einer bedingt vollziehbaren Geldstrafe von 90 Tagessätzen zu CHF 90.-- und zu einer Busse von CHF 3'000.-- verurteilt. X._ erhob gegen beide Entscheide Berufung. C.b. Das Appellationsgericht des Kantons Basel-Stadt sprach X._ mit Urteil vom 17. Juni 2015 des gewerbsmässigen Betrugs, der mehrfachen Verletzung der Verkehrsregeln, der groben Verletzung der Verkehrsregeln und des mehrfachen Fahrens in fahrunfähigem Zustand schuldig. Es verurteilte ihn zu einer bedingt vollziehbaren Freiheitsstrafe von 14 Monaten, zu einer bedingt vollziehbaren Geldstrafe von 90 Tagessätzen zu CHF 90.-- und zu einer Busse von CHF 2'000.--. D. X._ erhebt Beschwerde in Strafsachen. Er beantragt, er sei in teilweiser Aufhebung des Urteils des Appellationsgerichts vom 17. Juni 2015 vom Vorwurf des gewerbsmässigen Betrugs freizusprechen. Eventualiter sei er bloss des Betrugs statt des gewerbsmässigen Betrugs schuldig zu sprechen. Die Verurteilung wegen der SVG-Delikte ficht er nicht an. Er ersucht um Gewährung der unentgeltlichen Rechtspflege. Das Appellationsgericht des Kantons Basel-Stadt beantragt in seiner Stellungnahme die Abweisung der Beschwerde. Die Staatsanwaltschaft des Kantons Basel-Stadt hat unter Hinweis auf die Erwägungen im angefochtenen Entscheid auf Vernehmlassung verzichtet.