Sachverhalt: A. Der 1978 geborene Mazedonier A._ heiratete am 7. August 2004 in seinem Heimatland die 1961 geborene Schweizerin B._ und nahm am 17. Juli 2005 bei dieser Wohnsitz in der Schweiz. In der Folge erhielt er zum Verbleib bei seiner Ehefrau zunächst eine Aufenthaltsbewilligung und am 2. August 2010 die Niederlassungsbewilligung. Die kinderlos gebliebene Ehe wurde am 29. Oktober 2012 rechtskräftig geschieden. Während seines Aufenthalts in der Schweiz wurde A._ wiederholt straffällig und erwirkte folgende strafrechtliche Verurteilungen wegen Verbrechen und Vergehen: - Bestrafung mit einer Geldstrafe von 15 Tagessätzen zu je Fr. 90.-- und einer Busse von Fr. 1'000.-- wegen Fahrens eines Motorfahrzeugs in fahrunfähigem Zustand (qualifizierte Blutalkoholkonzentration) gemäss Strafbefehl der Staatsanwaltschaft Zürich-Limmat vom 18. April 2007; - Bestrafung mit einer Geldstrafe von 10 Tagessätzen zu je Fr. 90.-- und einer Busse von Fr. 800.-- wegen grober Verkehrsregelverletzung gemäss Strafbefehl des Bezirksamts Zofingen vom 22. Oktober 2008; - Bestrafung mit einer Freiheitsstrafe von 24 Monaten wegen gewerbsmässigen und bandenmässigen Diebstahls, mehrfacher Sachbeschädigung und mehrfachen Hausfriedensbruchs gemäss Urteil des Strafgerichts des Kantons Schwyz vom 18. Dezember 2014. Der Vollzug der Geld- und Freiheitsstrafen wurde jeweils zur Bewährung ausgesetzt. B. Nachdem es A._ bereits mit Verfügung vom 1. Juni 2007 wegen seiner Straffälligkeit ausländerrechtlich verwarnt hatte, widerrief das Migrationsamt mit Verfügung vom 5. Juni 2015 dessen Niederlassungsbewilligung und setzte ihm eine Ausreisefrist bis zum 31. August 2015. Überdies entzog es einem allfälligen Rekurs und dem Lauf der Rekursfrist die aufschiebende Wirkung. Den hiergegen erhobenen Rekurs wies die Sicherheitsdirektion des Kantons Zürich am 4. Dezember 2015 ab, soweit es diesen nicht als gegenstandslos betrachtete. Sodann setze es eine neue Ausreisefrist bis zum 16. März 2016. Die dagegen gerichtete Beschwerde von A._ wies das Verwaltungsgericht des Kantons Zürich mit Urteil vom 6. April 2016 ab. C. Mit Beschwerde vom 17. Mai 2016 beantragt A._ im Wesentlichen die Aufhebung des Urteils des Verwaltungsgerichts und den Verzicht auf den Widerruf der Niederlassungsbewilligung. Stattdessen sei er lediglich zu verwarnen. Ausserdem ersucht er um unentgeltliche Rechtspflege. Die Sicherheitsdirektion verzichtet auf eine Vernehmlassung zur Beschwerde. Das Verwaltungsgericht stellt den Antrag, die Beschwerde sei abzuweisen, soweit darauf eingetreten werde, und das Staatssekretariat für Migration schliesst auf Abweisung der Beschwerde. D. Mit Präsidialverfügung vom 18. Mai 2016 wurde der Beschwerde die aufschiebende Wirkung beigelegt.