Sachverhalt: A. A.a. Der kosovarische Staatsangehörige A.A._ (geb. 1974) heiratete im Jahre 1996 seine Landsfrau B._ (geb. 1975). Aus dieser Ehe gingen die drei Kinder B.A._ (geb. 1996), C.A._ (geb. 2000) und D.A._ (geb. 2001) hervor. Im Jahre 1998 reiste A.A._ illegal in die Schweiz ein und beantragte Asyl. Das (damalige) Bundesamt für Flüchtlinge (BFF) wies das Asylgesuch am 21. Juli 1998 ab, verfügte aber am 5. August 1999 die vorläufige Aufnahme. Im Februar 1999 war auch B.A._ (vermutlich mit ihrer Mutter) in die Schweiz eingereist und wurde vorläufig aufgenommen. Nach Aufhebung der vorläufigen Aufnahme reiste die Familie am 29. November 2000 in den Kosovo aus. Am 20. Dezember 2001 wurde die Ehe zwischen A.A._ und seiner Frau vom Bezirksgericht U._ (Kosovo) geschieden. Das Sorgerecht betreffend B.A._ wurde der Ehefrau zugeteilt, die beiden anderen Kinder wurden im Urteil nicht erwähnt. A.b. Am 5. April 2002 reiste A.A._ erneut illegal in die Schweiz ein und ersuchte wiederum um Asyl. Das BFF trat mit Verfügung vom 19. April 2002 auf das Gesuch nicht ein und wies A.A._ aus der Schweiz weg; dieser wurde am 25. April 2002 in den Kosovo zurückgeführt. A.c. Am 18. Januar 2008 stellte A.A._ ein Einreisegesuch zwecks Vorbereitung der Heirat mit der im Kanton Zürich niedergelassenen spanischen Staatsangehörigen C._ (geb. 1957). Mit Verfügung vom 5. August 2008 wies die Sicherheitsdirektion des Kantons Zürich das Gesuch ab, da Indizien auf eine Scheinehe hindeuteten. Dagegen erhob C._ Rekurs beim Regierungsrat. A.d. A.A._ reiste am 5. Dezember 2008 mit einer am 12. November 2008 ausgestellten Aufenthaltsbewilligung für Slowenien in die Schweiz ein, heiratete am 19. Januar 2009 in Kloten C._ und stellte ein Gesuch um Erteilung einer Aufenthaltsbewilligung zum Verbleib bei der Ehefrau. In der Folge erhielt A.A._ eine bis 1. August 2013 gültige Aufenthaltsbewilligung EG/EFTA, worauf der Rekurs an den Regierungsrat gegen die Verfügung vom 5. August 2008 abgeschrieben wurde. A.e. Mit Urteil des Kommunalgerichts V._ (Kosovo) vom 18. Januar 2010 wurde A.A._ das Sorgerecht über seine drei Kinder übertragen. Am 22. März 2010 stellte er für sie ein Gesuch um Bewilligung der Einreise in die Schweiz. Die Kinder reisten am 2. Januar 2011 ein, worauf ihnen - später bis zum 1. August 2013 verlängerte - Aufenthaltsbewilligungen EU/EFTA zum Verbleib beim Vater erteilt wurden. B. Mit Schreiben vom 3. Oktober 2011 gelangte C._ an das Migrationsamt und erklärte, sie habe ihren Ehemann und dessen Kinder am 3. März 2011 aus der Wohnung gewiesen, da sie entdeckt habe, dass A.A._ praktisch täglich mit seiner Ex-Frau telefonisch und per SMS kommuniziere und ihr gestanden habe, dass er mit dieser nach wie vor eine Beziehung führe. In weiteren Schreiben gab sie wiederum an, sie sei überzeugt, ihr Ehemann habe die Beziehung zu seiner Ex-Frau stets weitergeführt und sie lediglich benutzt, um für sich und seine Kinder zu einer Aufenthaltsbewilligung zu kommen. Per 1. März 2012 bezog A.A._ mit seinen Kindern eine eigene Wohnung. Mit Eheschutzurteil des Bezirksgerichts W._ vom 29. August 2012 wurde vom Getrenntleben der Ehegatten seit 1. März 2012 Vormerk genommen. Gestützt auf diesen Sachverhalt widerrief das Migrationsamt am 13. März 2013 die bis 1. August 2013 gültigen Aufenthaltsbewilligungen von A.A._ und seiner Kinder und setzte ihnen Frist zur Ausreise bis 30. Juni 2013. Die Verfügung wurde mit rechtskräftigem Urteil des Verwaltungsgerichts des Kantons Zürich vom 19. Dezember 2013 bestätigt unter Ansetzung einer neuen Ausreisefrist bis zum 28. Februar 2014. A.A._ und seine Kinder beachteten die Ausreisefrist nicht. Stattdessen reichte A.A._ am 25. Februar 2014 ein Gesuch um Erteilung einer Aufenthaltsbewilligung zum Verbleib bei C._ ein und machte geltend, er wohne wieder mit dieser zusammen. Das Migrationsamt teilte ihm mit Schreiben vom 11. März 2014 mit, diesem Begehren nicht entsprechen zu können. Am 29. Januar 2015 setzte das Migrationsamt A.A._ und seinen Kindern eine neue Ausreisefrist bis 28. Februar 2015. C. Am 25. Februar 2015 ersuchten A.A._ und seine Kinder erneut um eine Aufenthaltsbewilligung zum Verbleib bei C._. Das Migrationsamt trat am 2. März 2015 sinngemäss auf das Gesuch nicht ein und forderte A.A._ und seine Kinder auf, die Schweiz unverzüglich zu verlassen. Diese Verfügung wurde von der Sicherheitsdirektion (Entscheid vom 24. April 2015) und vom Verwaltungsgericht (Urteil vom 24. August 2015) bestätigt unter Ansetzung einer neuen Ausreisefrist bis 20. September 2015 bzw. bis 15 Tage ab dem Datum eines bestätigenden bundesgerichtlichen Entscheids. D. Mit Eingabe vom 1. Oktober 2015 erheben A.A._, B.A._, C.A._ und D.A._ gemeinsam Beschwerde in öffentlich-rechtlichen Angelegenheiten und Verfassungsbeschwerde an das Bundesgericht. Sie beantragen, in Aufhebung des angefochtenen Urteils sei ihnen der weitere Aufenthalt im Kanton Zürich zu bewilligen; eventuell sei die Sache an die Vorinstanz oder das Migrationsamt zurückzuweisen zur materiellen Behandlung des Gesuchs. Die Sicherheitsdirektion und das Verwaltungsgericht des Kantons Zürich verzichten auf Vernehmlassung. Das Staatssekretariat für Migration unterstützt den angefochtenen Entscheid. Mit Verfügung vom 29. Oktober 2015 hat der Präsident der II. öffentlich-rechtlichen Abteilung des Bundesgerichts der Beschwerde antragsgemäss die aufschiebende Wirkung zuerkannt.