Sachverhalt: A. A._ ist im Besitz einer Taxihalterbewilligung A sowie einer Taxichauffeurbewilligung im Kanton Basel-Stadt. Aufgrund wiederholter Verstösse gegen das Gesetz des Kantons Basel-Stadt vom 17. Januar 1996 über den Betrieb von Taxis (Taxigesetz; SG 563.200) stellte ihm das Taxibüro der Kantonspolizei Basel-Stadt am 28. April 2008 den Entzug der Taxihalterbewilligung in Aussicht. Das Verfahren wurde am 30. September 2008 bis zum Vorliegen eines rechtskräftigen Strafurteils sistiert. Nachdem weitere Vorkommnisse hinzugetreten waren, verfügte das Taxibüro am 3. August 2011 nach Gewährung des rechtlichen Gehörs den Entzug der Taxihalterbewilligung und drohte A._ den Entzug der Taxichauffeurbewilligung an, für den Fall, dass sein Verhalten in den nächsten zwei Jahren (bis 1. September 2013) erneut Anlass zu Klagen geben sollte. Das Taxibüro begründete seine Verfügung mit einem offenen Verfahren bei der Kantonspolizei wegen manipulierter Fahrtschreiber, einer Verurteilung durch das Polizeigericht U._/F, Widerhandlungen gegen das Taxigesetz (unzulässige Kundenanwerbung am Flughafen Basel/Mulhouse) sowie drei Verurteilungen durch das Strafgericht Basel-Stadt. Die dagegen erhobenen kantonalen Rechtsmittel sind erfolglos geblieben (Entscheid des Justiz- und Sicherheitsdepartements des Kantons Basel-Stadt vom 18. September 2014; Urteil des Appellationsgerichts des Kantons Basel-Stadt vom 16. November 2015). B. Am 4. Januar 2016 erhebt A._ Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht und beantragt die Aufhebung des Urteils des Appellationsgerichts. Das Appellationsgericht beantragt die Abweisung der Beschwerde, soweit darauf einzutreten sei. Das Justiz- und Sicherheitsdepartement schliesst auf Abweisung sowohl der Beschwerde als auch des Gesuchs um Erteilung der aufschiebenden Wirkung. Das Taxibüro hat sich nicht vernehmen lassen. Mit Verfügung vom 22. März 2016 wurde das Gesuch um aufschiebende Wirkung abgewiesen.