Sachverhalt: A. Am 21. November 2009 ging auf einem Mobiltelefon bei der Polizei die SMS ein: "Hallo koleg ich bin J._ und das ist meine new number ok". Drei Tage später antwortete der Polizist Y._ mittels SMS, um ein Treffen zu vereinbaren und den Absender zu identifizieren. Daraufhin konnte J._ (alias Z._) bis zur A._-Strasse in B._ gefolgt und angehalten werden. Anlässlich der Durchsuchung der Wohnung, zu der er den Schlüssel besass, konnten u.a. Betäubungsmittel sichergestellt werden. Auf der Verpackung waren Finger- bzw. Handflächenabdrücke von X._. Der bei einer Hausdurchsuchung am 17. Januar 2010 an der C._-Strasse in B._ beschlagnahmte Gummihandschuh, der zum Strecken von Heroin verwendet worden war, wies DNA-Spuren von X._ auf. X._ wurde wegen des Verdachts der qualifizierten Widerhandlung gegen das Betäubungsmittelgesetz verhaftet. Sein Verteidiger beantragte der Staatsanwaltschaft, gewisse Aufzeichnungen betreffend eine mutmasslich zum Drogenhandel benutzte Wohnung (A._-Strasse in B._) aus den Akten zu entfernen und unter Verschluss zu halten oder zu vernichten. Im Zusammenhang mit der Wohnung an der C._-Strasse in B._ sei zu dokumentieren, wie es dazu gekommen sei, dass die Polizei einen Hinweis erhalten habe, wonach Streckmittel angeliefert würden. Die Staatsanwaltschaft wies die Anträge ab. Die von X._ gegen diesen Entscheid erhobene Beschwerde wies das Appellationsgericht des Kantons Basel-Stadt ab. Mangels nicht wieder gutzumachenden Rechtsnachteils trat das Bundesgericht auf die Beschwerde von X._ nicht ein (Verfahren 1B_325/2011). B. Das Strafgericht des Kantons Basel-Stadt verurteilte X._ am 13. Oktober 2011 wegen mehrfacher qualifizierter Widerhandlung gegen das Betäubungsmittelgesetz zu einer Freiheitsstrafe von 4 1⁄2 Jahren. Vom Vorwurf der mehrfachen Widerhandlung gegen das Ausländergesetz sprach es ihn frei. Es entschied über die Einziehung der beschlagnahmten Gegenstände. Auf Berufung von X._ hin bestätigte das Appellationsgericht des Kantons Basel-Stadt am 16. Mai 2013 das Urteil des Strafgerichts. C. X._ beantragt mit Beschwerde in Strafsachen, den Entscheid des Appellationsgerichts teilweise aufzuheben. Er sei vom Vorwurf der qualifizierten Widerhandlung gegen das Betäubungsmittelgesetz freizusprechen und unverzüglich auf "freien Fuss" zu setzen. Eventualiter sei er zu einer Freiheitsstrafe von 3 1⁄2 Jahren zu verurteilen und unverzüglich auf "freien Fuss" zu setzen. Subeventualiter sei die Angelegenheit zur neuen Entscheidung an die Vorinstanz zurückzuweisen. X._ ersucht um unentgeltliche Rechtspflege. D. Das Appellationsgericht beantragt die Abweisung der Beschwerde und verweist grundsätzlich auf die Erwägungen im angefochtenen Entscheid. Die Staatsanwaltschaft stellt mit Eingabe vom 22. Oktober 2013 den Antrag, die Beschwerde sei abzuweisen. X._ verzichtet auf eine Stellungnahme.