Sachverhalt: A. Am 9. September 2008 erklärte das Strafgericht Basel-Stadt X._ der qualifizierten Widerhandlung gegen das Betäubungsmittelgesetz, der versuchten Geldwäscherei, der mehrfachen einfachen Widerhandlung gegen das Betäubungsmittelgesetz und der Hinderung einer Amtshandlung schuldig und verurteilte ihn zu einer Freiheitsstrafe von vier Jahren. Gegen diesen Entscheid erhob X._ Appellation an das Appellationsgericht des Kantons Basel-Stadt. Am 19. August 2009 bestätigte dieses das erstinstanzliche Urteil. B. X._ führt Beschwerde in Strafsachen beim Bundesgericht. Er beantragt, das Urteil des Appellationsgerichts des Kantons Basel-Stadt sei aufzuheben, und er sei freizusprechen. Eventualiter sei die Sache zur Neubeurteilung an die Vorinstanz zurückzuweisen, und diese sei gestützt auf Art. 9 Abs. 3 BÜPF anzuweisen, die rückwirkend erhobenen Randdaten der Mobiltelefonnummer xxx xxx xx xx vom 3. November 2006 bis 3. April 2007 sowie sämtliche Erkenntnisse und Folgebeweise, die auf die Erhebung dieser rückwirkenden Randdaten zurückzuführen seien, aus den Akten zu entfernen. Der Beschwerdeführer stellt ausserdem das Gesuch um Gewährung der unentgeltlichen Prozessführung und Verbeiständung. Zudem sei ihm für das bundesgerichtliche Verfahren zu Lasten der Vorinstanz eine Parteientschädigung zuzusprechen. C. Die Staatsanwaltschaft des Kantons Basel-Stadt beantragt die kostenfällige Abweisung der Beschwerde. Die Vorinstanz beantragt die Abweisung der Beschwerde, soweit auf diese einzutreten sei.