Sachverhalt: A. A.a X._, türkischer Staatsangehöriger, geboren am 5. Mai 1973, heiratete am 29. Juni 2001 die Schweizer Bürgerin Y._ und erhielt in der Folge eine Aufenthaltsbewilligung im Rahmen des Familiennachzugs, die indessen im Jahre 2006 nicht mehr verlängert wurde. Am 2. März 2007 wurde die Ehe von X._ und Y._ geschieden, worauf X._ am 11. April 2007 die in der Schweiz niedergelassene portugiesische Staatsangehörige Z._, geboren am 19. Dezember 1963, heiratete und in der Folge eine Aufenthaltsbewilligung EG/EFTA erhielt. A.b Am 29. November 2010 stellten X._ und Z._ das Gesuch um Familiennachzug der in der Türkei lebenden Kinder von X._, A._ (geboren am 10. Dezember 1993), B._ (geboren am 23. Januar 1996) und C._ (geboren am 4. Mai 1997). Das Migrationsamt des Kantons St. Gallen wies das Gesuch am 23. September 2011 ab. B. X._, A._, B._ und C._ erhoben dagegen erfolglos Rekurs an das Sicherheits- und Justizdepartement (Entscheid vom 20. März 2012) und an das Verwaltungsgericht des Kantons St. Gallen (Urteil vom 15. Oktober 2012). C. X._, A._, B._ und C._ erheben mit Eingabe vom 19. November 2012 Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht. Sie beantragen, das Urteil des Verwaltungsgerichts sei aufzuheben und es sei das Migrationsamt anzuweisen, den Kindern A._, B._ und C._ eine Aufenthaltsbewilligung zum Verbleib beim Vater und dessen Ehefrau zu erteilen. Das Sicherheits- und Justizdepartement und das Verwaltungsgericht St. Gallen sowie das Bundesamt für Migration beantragen Abweisung der Beschwerde.