Sachverhalt: A. X._ (geb. 27. April 1978) stammt aus dem Kosovo. Er reiste am 28. Januar 1991 im Rahmen des Familiennachzugs in die Schweiz ein und erhielt in der Folge eine Niederlassungsbewilligung zum Verbleib bei seinen Eltern. B. Während seines Aufenthalts in der Schweiz erwirkte X._ verschiedene strafrechtliche Verurteilungen. Mit Urteil und Beschluss des Bezirksgerichts Zürich vom 22. Januar 2003 wurde er unter anderem wegen betrügerischen Missbrauchs einer Datenverarbeitungsanlage, mehrfachen Diebstahls, mehrfacher Sachbeschädigung und mehrfacher Hehlerei mit acht Monaten Gefängnis bedingt unter Ansetzung einer Probezeit von drei Jahren bestraft. Am 24. November 2005 wurde er unter anderem wegen banden- und gewerbsmässigen, teilweise versuchten Diebstahls zu zwölf Monaten Gefängnis unter Ansetzung einer Probezeit von vier Jahren verurteilt. Am 29. April 2003 und 10. März 2006 verwarnte die Ausländerbehörde X._. Am 19. August 2008 wurde X._ in Österreich verhaftet. Am 14. November 2008 verurteilte ihn das Landgericht Korneuburg wegen Verbrechens des Suchtgifthandels zu einer Freiheitsstrafe von vier Jahren. Am 19. November 2010 wurde er aus dem Strafvollzug in Österreich entlassen. Mit Verfügung vom 5. März 2012 stellte das Migrationsamt fest, dass die Niederlassungsbewilligung von X._ erloschen sei, und wies ihn aus der Schweiz weg. C. Einen hiergegen gerichteten Rekurs wies die Sicherheitsdirektion des Kantons Zürich am 23. November 2012 ab. Die gegen den Entscheid der Sicherheitsdirektion erhobene Beschwerde wies das Verwaltungsgericht des Kantons Zürich mit Urteil vom 17. April 2013 ab. D. Mit Eingabe vom 3. Juni 2013 erhebt X._ Beschwerde beim Bundesgericht und beantragt, es sei das Urteil vom 17. April 2013 aufzuheben. Ihm sei eine Aufenthaltsbewilligung zu erteilen; eventualiter sei die Sache zur Neubeurteilung an die Vorinstanz zurückzuweisen. Die Sicherheitsdirektion des Kantons Zürich hat darauf verzichtet, sich vernehmen zu lassen. Das Verwaltungsgericht beantragt, die Beschwerde abzuweisen, soweit darauf einzutreten sei. Das Bundesamt für Migration beantragt die Abweisung der Beschwerde. Mit Verfügung vom 7. Juni 2013 hat der Präsident der II. öffentlich-rechtlichen Abteilung der Beschwerde antragsgemäss aufschiebende Wirkung zuerkannt. 