Sachverhalt: A. A.A._ (geb. 1986) ist philippinische Staatsangehörige. Ihre im Jahre 2005 geborene Tochter B.A._ wurde im August 2006 vom Schweizer Bürger C._ (geb. 1962) in den Philippinen anerkannt. Zu einem späteren Zeitpunkt wurde die Kindesanerkennung in die schweizerischen Zivilstandsregister eingetragen. Am 6. August 2008 reiste A.A._ zusammen mit ihrer Tochter zwecks Eheschliessung mit C._ in die Schweiz ein. Die Heirat fand am 26. Februar 2009 im Kanton Basel-Stadt statt. In der Folge erhielt A.A._ eine Aufenthaltsbewilligung zum Verbleib beim Ehemann. Mit Eheschutzverfügung vom 26. November 2009 bewilligte das Zivilgericht Basel-Stadt den Ehegatten das Getrenntleben. Am 23. August 2011 wurde die Ehe geschieden und im Rahmen einer Vaterschaftsanfechtung das Kindesverhältnis zwischen B.A._ und C._ aufgehoben. Dies führte zum Verlust des Schweizer Bürgerrechts von B.A._. Ein Gesuch um erleichterte Einbürgerung von B.A._ ist hängig. B. Am 8. Dezember 2011 verfügte das Migrationsamt des Kantons Basel-Stadt die Nichtverlängerung der Aufenthaltsbewilligung von A.A._ und wies sie aus der Schweiz weg. Ein gegen diese Verfügung erhobener Rekurs beim Justiz- und Sicherheitsdepartement des Kantons Basel-Stadt blieb erfolglos (Entscheid vom 3. Oktober 2012). Mit Urteil vom 22. August 2014 wies das Appellationsgericht des Kantons Basel-Stadt den von A.A._ und B.A._ gegen den Departementsentscheid erhobenen Rekurs ebenfalls ab. C. Vor Bundesgericht beantragen A.A._ und B.A._, das vorinstanzliche Urteil sei aufzuheben und die Sache an die Vorinstanzen zur Regelung des Aufenthalts und der unentgeltlichen Rechtspflege sowie zur Festlegung eines Kostenerlasshonorars durch die erste Beschwerdeinstanz zurückzuweisen. Zudem ersuchen sie um unentgeltliche Rechtspflege und Verbeiständung für das Verfahren vor Bundesgericht. Das Justiz- und Sicherheitsdepartement des Kantons Basel-Stadt, das Appellationsgericht Basel-Stadt sowie das Bundesamt für Migration (seit dem 1. Januar 2015: Staatssekretariat für Migration SEM) beantragen die Abweisung der Beschwerde. Mit Präsidialverfügung vom 17. Oktober 2014 wurde der Beschwerde antragsgemäss aufschiebende Wirkung zuerkannt.