Sachverhalt: A. A.a. Der kosovarische Staatsangehörige A._ (geb. 1990) reiste am 24. November 2004 im Rahmen des Familiennachzugs zu seinen Eltern in die Schweiz ein. A.b. Mit Urteil vom 16. April 2009 verurteilte das Jugendstrafgericht Basel-Stadt A._ wegen versuchter vorsätzlicher Tötung, versuchter schwerer Körperverletzung und einfacher Körperverletzung zu einer Freiheitsstrafe von 15 Monaten. Der Vollzug der Strafe wurde zugunsten einer Unterbringung in einer geschlossenen Einrichtung aufgeschoben. Am 21. September 2009 verwarnte das Migrationsamt des Kantons Basel-Stadt A._ wegen des ausgesprochenen Freiheitsentzugs; die Niederlassungsbewilligung wurde nicht widerrufen, indes drohte das Migrationsamt A._ den Widerruf für den Fall an, dass er erneut straffällig werden sollte. A.c. Mit Urteil vom 31. Januar 2013 verurteilte das Strafgericht Basel-Stadt A._ wegen mehrfacher Drohung zu einer unbedingten Freiheitsstrafe von fünf Monaten. Mit Verfügung vom 11. März 2013 verweigerte das Amt für Justizvollzug die bedingte Entlassung von A._ aus dem Strafvollzug mit der Begründung, dass nicht angenommen werden könne, dass dieser keine weiteren Verbrechen und Vergehen verüben werde. Am 19. Mai 2013 wurde A._ - nach Verbüssung der gesamten Freiheitsstrafe - aus dem Strafvollzug entlassen. B. Nach Gewährung des rechtlichen Gehörs verfügte das Migrationsamt am 11. Juni 2013 den Widerruf der Niederlassungsbewilligung von A._ und wies ihn aus der Schweiz weg. Die dagegen erhobenen kantonalen Rechtsmittel blieben in materieller Hinsicht ohne Erfolg (Entscheid des Justiz- und Polizeidepartementes des Kantons Basel-Stadt vom 29. November 2013, Urteil des Appellationsgerichts des Kantons Basel-Stadt als Verwaltungsgericht vom 28. Januar 2015). Im Kostenpunkt gewährte das Appellationsgericht die unentgeltliche Rechtspflege für das vorinstanzliche Verfahren wie auch für das Verfahren vor dem Departement. C. Mit Eingabe vom 12. Mai 2015 erhebt A._ Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht. Er beantragt, das Urteil des Appellationsgerichts vom 28. Januar 2015 und die Verfügung des Migrationsamtes vom 11. Juni 2013 seien aufzuheben. Weiter sei dem Beschwerdeführer die unentgeltliche Rechtspflege für das bundesgerichtliche Verfahren zu bewilligen. D. Das Appellationsgericht und das Justiz- und Sicherheitsdepartement des Kantons Basel-Stadt sowie das Staatssekretariat für Migration schliessen auf Abweisung der Beschwerde. Der Beschwerdeführer repliziert. Mit Verfügung vom 15. Mai 2015 hat der Präsident der II. öffentlich-rechtlichen Abteilung des Bundesgerichts der Beschwerde antragsgemäss die aufschiebende Wirkung zuerkannt.