Sachverhalt:
A.
Das Strafgericht Basel-Stadt erklärte A._ am 2. November 2017 des qualifizierten Raubes zum Nachteil von B._ schuldig. Es bestrafte ihn mit einer Freiheitsstrafe von 5 Jahren. Gleichzeitig ordnete es eine ambulante psychiatrische Behandlung an. Im Zivilpunkt verpflichtete es A._, B._ eine Genugtuung in der Höhe von Fr. 1'500.-- zu bezahlen. Gegen dieses Urteil erhob A._ Berufung.
B.
Das Appellationsgericht des Kantons Basel-Stadt bestätigte am 13. November 2018 das erstinstanzliche Urteil. A._ führt Beschwerde in Strafsachen. Er beantragt, das Urteil des Appellationsgerichts sei aufzuheben und er sei wegen nicht qualifizierten Raubes zu einer bedingten Freiheitsstrafe von 6 Monaten zu verurteilen. Eventualiter sei die Sache an die Vorinstanz zurückzuweisen und diese anzuweisen, ein Obergutachten einzuholen. Die Genugtuung an B._ sei auf Fr. 500.-- festzusetzen. Für das Verfahren vor dem Bundesgericht sei ihm die unentgeltliche Rechtspflege und Verbeiständung zu gewähren.
C.
Das Appellationsgericht und die Staatsanwaltschaft des Kantons Basel-Stadt beantragen, die Beschwerde sei abzuweisen. B._ reichte keine Vernehmlassung ein.

Erwägungen:
1.
1.1.
Der Beschwerdeführer rügt unter anderem, dass die Vorinstanz den Sachverhalt willkürlich feststelle. Es sei nicht erstellt, wo und wie er das Messer an den Hals von B._ angesetzt haben soll, sofern dies überhaupt der Fall war. Zudem seien am Hals des Opfers keine Spuren des Messers festgestellt worden. Dem Umstand, dass er gegenüber der Polizei gesagt haben soll, er habe B._ das Messer an den Hals gehalten und die Möglichkeit gehabt, durchzuziehen, komme kein Beweiswert zu. Das Vorliegen einer Lebensgefahr im Sinne von <ref-law> sei zu keinem Zeitpunkt der Tat nachgewiesen.
1.2. Die Vorinstanz erwägt diesbezüglich im Wesentlichen, B._ habe mehrmals geschildert, dass ihm das Messer an den Hals gehalten worden sei und er dieses gespürt habe. Er habe aber nicht sagen können, welchen Teil des Messers er gespürt habe. Dies entlaste aber den Beschwerdeführer nicht. Einerseits sei es logisch, dass der von hinten angegriffene B._ das Messer nicht gesehen habe. Andererseits sei abwegig, dass B._ mit dem Griffteil des Messers anstatt mit der Spitze bedroht worden wäre. Dass der Beschwerdeführer dem Geschädigten B._ das Messer an den Hals hielt, ergebe sich bereits aus dem Polizeirapport bzw. aus dem Pikett-Bericht der Staatsanwaltschaft. Dass das Messer zeitweise seinen Hals berührt habe, habe B._ auch anlässlich der erstinstanzlichen Hauptverhandlung bestätigt. Die nebelhafte Aussage des Beschwerdeführers im Rahmen derselben Verhandlung ("Ich denke nicht, dass ich die Klinge an den Hals anlegte, aber ich kann es nicht mit 100% Sicherheit sagen") ändere nichts an der Glaubhaftigkeit der Aussagen von B._, zumal der Beschwerdeführer am Tattag gegenüber der Polizei gesagt habe, dass er das Messer B._ an den Hals gehalten habe und die Möglichkeit gehabt hätte, "durchzuziehen" (Urteil, S. 8).
1.3. Nach <ref-law> weisen Polizei oder Staatsanwaltschaft die beschuldigte Person zu Beginn der ersten Einvernahme in einer ihr verständlichen Sprache darauf hin, dass gegen sie ein Vorverfahren eingeleitet worden ist und welche Straftaten Gegenstand des Verfahrens bilden (lit. a); sie die Aussage und die Mitwirkung verweigern kann (lit. b); sie berechtigt ist, eine Verteidigung zu bestellen oder gegebenenfalls eine amtliche Verteidigung zu beantragen (lit. c); sie eine Übersetzerin oder einen Übersetzer verlangen kann (lit. d). Einvernahmen ohne diese Hinweise sind nicht verwertbar (<ref-law>). Dass die Belehrung stattfand, ist im Protokoll zu vermerken (<ref-law>).
Die Aussage des Beschwerdeführers, wonach er die Möglichkeit gehabt hätte, mit dem Messer "durchzuziehen", ist einzig im Polizeirapport vom 1. Juli 2015 (kantonale Akten, pag. 46 ff.) wiedergegeben. Ob eine Befragung einzig in der Form eines Polizeirapports überhaupt zulässig ist, kann offenbleiben. Jedenfalls fand eine Belehrung gemäss <ref-law> nicht statt, womit die zur Diskussion stehende Erklärung des Beschwerdeführers nicht verwertbar ist (vgl. NIKLAUS RUCKSTUHL, in: Basler Kommentar, Schweizerische Strafprozessordnung, 2. Aufl. 2014, N. 7 zu <ref-law>). Die Rüge des fehlenden Beweiswerts dieser Erklärung erweist sich damit - im Ergebnis - als begründet. Der angefochtene Entscheid ist bereits aus diesem Grund aufzuheben und die Sache an die Vorinstanz zurückzuweisen, damit diese feststellt, ob und gegebenenfalls wie der Beschwerdeführer das Messer an den Hals von B._ hielt und entsprechend ihrer Erkenntnis einen neuen Entscheid fällt. Es erübrigt sich damit, auf die weiteren Rügen des Beschwerdeführers einzugehen.
2.
Die Beschwerde ist gutzuheissen. Der angefochtene Entscheid ist aufzuheben und die Sache zu neuer Entscheidung an die Vorinstanz zurückzuweisen.
Für das bundesgerichtliche Verfahren sind keine Kosten zu erheben (Art. 66 Abs. 1 und 4 BGG). Der Beschwerdeführer hat Anspruch auf eine angemessene Parteientschädigung (<ref-law>). Diese ist praxisgemäss dem Rechtsvertreter auszurichten. Das Gesuch des Beschwerdeführers um unentgeltliche Rechtspflege und Verbeiständung wird gegenstandslos.

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird gutgeheissen. Das Urteil des Appellationsgerichts Basel-Stadt vom 13. November 2018 wird aufgehoben und die Sache zu neuer Entscheidung an die Vorinstanz zurückgewiesen.
2.
Es werden keine Kosten erhoben.
3.
Der Kanton Basel-Stadt hat dem Rechtsvertreter des Beschwerdeführers, Advokat Urs Grob, eine Parteientschädigung von Fr. 3'000.-- zu bezahlen.
4.
Dieses Urteil wird den Parteien und dem Appellationsgericht des Kantons Basel-Stadt, Kammer, schriftlich mitgeteilt.
Lausanne, 5. Dezember 2019
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Denys
Der Gerichtsschreiber: Moses