Sachverhalt: A. X._ und Y._ reisten am 19. August 2017 mit dem Fahrzeug beim Grenzübergang Riehen von Deutschland in die Schweiz ein. Y._ lenkte das Fahrzeug, X._ sass auf dem Beifahrersitz. Im Fussraum auf der Beifahrerseite war hinter einer Abdeckung ein eingeschweisstes, mit Klebeband umwickeltes Paket versteckt. Darin befand sich 493.5 Gramm Kokaingemisch mit einem Reinheitsgrad von 86%. B. Am 07. Februar 2018 verurteilte das Strafgericht des Kantons Basel-Stadt X._ wegen mengenmässig qualifizierter Widerhandlungen gegen das Betäubungsmittelgesetz, mehrfacher rechtswidriger Einreise und rechtswidrigen Aufenthalts zu einer Freiheitsstrafe von 6 Jahren, unter Widerruf der bedingten Entlassung und Einbezug der Reststrafen gemäss Urteil des Obergerichts des Kantons Solothurn vom 20. Juni 2012 von 3 Jahren und 309 Tagen und gemäss Strafbefehl der Staatsanwaltschaft Limmattal/Albis vom 20. Februar 2016 von 61 Tagen. Das Gericht verwies X._ für 10 Jahre des Landes, ordnete die Eintragung der Landesverweisung im Schengener Informationssystem an und auferlegte ihm die Verfahrenskosten. C. Das Appellationsgericht des Kantons Basel-Stadt bestätigte mit Urteil vom 27. November 2018 den Schuldspruch wegen mengenmässig qualifizierter Widerhandlungen gegen das Betäubungsmittelgesetz und stellte im Übrigen fest, dass der erstinstanzliche Schuldspruch wegen mehrfacher rechtswidriger Einreise und rechtswidrigen Aufenthalts in Rechtskraft erwachsen war. Es widerrief die X._ gewährte bedingte Entlassung aus dem Strafvollzug betreffend das Urteil des Obergerichts des Kantons Solothurn vom 20. Juni 2012 (Reststrafe von 3 Jahren und 309 Tagen) und ordnete die Rückversetzung in den Strafvollzug an. Hingegen verzichtete es auf einen Widerruf der bedingten Entlassung aus dem Strafvollzug betreffend den Strafbefehl der Staatsanwaltschaft Limmattal/Albis vom 20. Februar 2016 (Reststrafe von 61 Tagen). Das Gericht bestrafte X._ unter Einbezug der als vollziehbar erklärten Reststrafe zu einer Gesamtfreiheitsstrafe von 6 Jahren und 9 Monaten, unter Anrechnung des bisher ausgestandenen Freiheitsentzugs. Weiter verwies es X._ für 10 Jahre des Landes und ordnete die Eintragung im Schengener Informationssystem an, unter Auferlegung der Verfahrenskosten an den Beschuldigten. D. Gegen dieses Urteil erhebt X._ Beschwerde in Strafsachen. Er beantragt, das angefochtene Urteil sei aufzuheben und er sei vom Vorwurf der qualifizierten Widerhandlung gegen das Betäubungsmittelgesetz freizusprechen. Die Rückversetzung in den Strafvollzug, die Landesverweisung und deren Eintrag im Schengener Informationssystem seien aufzuheben. Er sei umgehend aus der Haft zu entlassen und für die erlittene Überhaft mit Fr. 150.00 pro Hafttag zu entschädigen. Die erst- und zweitinstanzlichen Verfahrenskosten seien neu zu verteilen. Eventualiter sei die Sache zur neuen Beurteilung an das Appellationsgericht des Kantons Basel-Stadt zurückzuweisen. Es sei ihm die unentgeltliche Rechtspflege und Verbeiständung zu gewähren, unter Kosten- und Entschädigungsfolgen zu Lasten des Kantons Basel-Stadt.