Sachverhalt: A. A.A._ (geb. 1982) ist mazedonischer Staatsangehöriger. Er reiste am 16. August 1991 im Rahmen des Familiennachzugs in die Schweiz ein und ist im Besitz einer Niederlassungsbewilligung. Am 25. April 2007 heiratete er in seiner Heimat die Landsfrau B.A._ (geb. 1983), welche in der Folge eine Aufenthaltsbewilligung zum Verbleib bei ihrem Ehemann in der Schweiz erhielt. Aus der Ehe sind zwei Kinder hervorgegangen, C.A._ (geb. 2010) und D.A._ (geb. 2012), welche über die Niederlassungsbewilligung verfügen. Während seines Aufenthalts in der Schweiz trat A.A._ strafrechtlich wie folgt in Erscheinung: - Strafbefehl der Bezirksanwaltschaft Zürich vom 20. August 2003: bedingt vollziehbare Busse von Fr. 200.--, unter Ansetzung einer Probezeit von einem Jahr, wegen Hausfriedensbruchs; - Strafbefehl der Staatsanwaltschaft Zürich-Sihl vom 11. Januar 2005: bedingte Gefängnisstrafe von 90 Tagen, unter Ansetzung von einer Probezeit von drei Jahren, sowie Busse von Fr. 600.-- wegen mehrfachen Vergehens gegen das Betäubungsmittelgesetz, der Fälschung von Ausweisen, des Missbrauchs von Ausweisen und Schildern, des Fahrens in angetrunkenem Zustand, der Entwendung zum Gebrauch sowie des Fahrens ohne Führerausweis; - Strafbefehl der Staatsanwaltschaft Zürich-Sihl vom 17. März 2005: Haft von sechs Tagen wegen mehrfacher Übertretung des Betäubungsmittelgesetzes; - Urteil des Bezirksgerichts Zürich vom 25. Januar 2006: Gefängnisstrafe von 60 Tagen wegen Gewalt und Drohung gegen Behörden und Beamte sowie mehrfacher Übertretung des Betäubungsmittelgesetzes; gleichzeitig wurde er bezüglich der bedingt aufgeschobenen Gefängnisstrafe gemäss Strafbefehl der Staatsanwaltschaft Zürich-Sihl vom 11. Januar 2005 verwarnt; - Strafbefehl der Staatsanwaltschaft Zürich-Limmat vom 15. Mai 2006: bedingte Gefängnisstrafe von 90 Tagen, unter Ansetzung einer Probezeit von vier Jahren, sowie Busse von Fr. 500.-- wegen mehrerer Tätlichkeiten, mehrerer versuchter Tätlichkeiten, fahrlässiger Körperverletzung sowie mehrfacher Übertretung des Betäubungsmittelgesetzes; die früher bedingt ausgesprochenen Gefängnisstrafen von 90 und 60 Tagen wurden in der Folge vollzogen; - Strafbefehl der Staatsanwaltschaft Zürich-Limmat vom 16. Januar 2008: 240 Stunden gemeinnützige Arbeit sowie Busse von Fr. 300.-- wegen Entwendung zum Gebrauch und mehrfacher Vergehen und Übertretungen gegen das Betäubungsmittelgesetz; - Strafbefehl der Staatsanwaltschaft Zürich-Sihl vom 8. Juni 2011: Geldstrafe von 120 Tagessätzen zu je Fr. 30.-- wegen vorsätzlichen Fahrens in fahrunfähigem Zustand sowie der fahrlässigen Verletzung von Verkehrsregeln; - Urteil des Bezirksgerichts Zürich vom 26. Oktober 2011: Freiheitsstrafe von acht Monaten sowie Busse von Fr. 300.-- wegen vorsätzlicher Entwendung zum Gebrauch, vorsätzlichen Fahrens in fahrunfähigem Zustand, vorsätzlichen Fahrens ohne Führerausweis sowie mehrfacher Übertretung des Betäubungsmittelgesetzes. Am 15. Februar 2005 und am 19. Februar 2006 wurde A.A._ ausländerrechtlich verwarnt. B. Mit Verfügung vom 6. Mai 2013 widerrief das Migrationsamt des Kantons Zürich die Niederlassungsbewilligung von A.A._ und wies das Gesuch von B.A._ um Verlängerung ihrer Aufenthaltsbewilligung ab. Beide wurden aus der Schweiz ausgewiesen. Ein dagegen erhobener Rekurs bei der Sicherheitsdirektion blieb erfolglos (Entscheid vom 11. August 2014). Mit Urteil vom 10. Februar 2015 wies das Verwaltungsgericht des Kantons Zürich die dagegen erhobene Beschwerde ebenfalls ab. C. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 27. April 2015 beantragen A.A._ und B.A._ die Aufhebung des angefochtenen Urteils. Der Widerruf der Niederlassungsbewilligung von A.A._ sei aufzuheben und die Aufenthaltsbewilligung von B.A._ sei zu verlängern. Zudem ersuchen sie um unentgeltliche Rechtspflege und Verbeiständung. Während die Sicherheitsdirektion auf Vernehmlassung verzichtet, beantragen das Verwaltungsgericht und das Staatssekretariat für Migration die Abweisung der Beschwerde. Das Migrationsamt liess sich nicht vernehmen. Mit Präsidialverfügung vom 28. April 2015 wurde der Beschwerde antragsgemäss aufschiebende Wirkung zuerkannt.