Sachverhalt: A. X._ (geb. 1967) stammt aus Jordanien. Am 12. Oktober 1998 reiste er in die Schweiz ein und beantragte Asyl. Im Mai 2000 lernte er die 13 Jahre ältere Z._ kennen. Die beiden heirateten im Dezember 2000. In der Folge erhielt X._ eine Aufenthaltsbewilligung und zog sein Gesuch um Asyl zurück. B. Im September 2003 stellt X._ ein Gesuch um erleichterte Einbürgerung. Seit dem 1. November 2003 verfügte er über eine Zweitwohnung in der Nähe der ehelichen Wohnung. Dem Gesuch um Einbürgerung wurde am 24. Juni 2004 stattgegeben. Am 8. Oktober 2004 wurden Eheschutzmassnahmen angeordnet und das Getrenntleben gerichtlich festgestellt. Im Februar 2005 reichten die Ehegatten ein gemeinsames Scheidungsbegehren ein; am 6. Juni 2005 wurde die Ehe geschieden. Das Bundesamt für Migration teilte X._ in der Folge mit, es erwäge die Nichtigerklärung der erleichterten Einbürgerung. C. Am 16. Dezember 2005 heiratete X._ die Jordanierin Y._. Z._ war mittlerweile - die Vorinstanz hat nicht festgestellt, an welchem Datum - verstorben. Am 19. April 2006 reichte X._ ein erstes, am 28. Mai 2010 ein weiteres Gesuch um Familiennachzug für seine jordanische Ehegattin ein. Dem zweiten Gesuch wurde am 29. Juli 2010 stattgegeben. Am 6. August 2010 reiste Y._ in die Schweiz ein und erhielt eine Aufenthaltsbewilligung. Am 6. Juli 2011 wurden dem Ehepaar in St. Gallen die beiden Kinder A._ und B._ geboren. D. Mit Verfügung vom 1. Mai 2009 erklärte das Bundesamt für Migration die im Jahr 2004 erfolgte erleichterte Einbürgerung für nichtig. Das Bundesgericht wies eine hiergegen erhobene Beschwerde letztinstanzlich ab (Urteil 1C_476/2010 vom 13. Dezember 2010). Bereits zuvor, am 17. Oktober 2010, stellte X._ ein Gesuch um Wiedererteilung einer Aufenthaltsbewilligung. Am 5. Januar 2011 ersuchte er um Erteilung einer Niederlassungsbewilligung. Das Migrationsamt wies die Gesuche um Erteilung einer Aufenthalts- bzw. einer Niederlassungsbewilligung mit Verfügung vom 21. März 2011 ab. X._ und seine Gattin erhoben hiergegen Rekurs beim Sicherheits- und Justizdepartement des Kantons St. Gallen, welches diesen am 9. März 2012 abwies. Eine hiergegen gerichtete Beschwerde an das Verwaltungsgericht des Kantons St. Gallen blieb ohne Erfolg (Urteil vom 15. Oktober 2012). E. Mit Eingabe vom 11. November 2012 erheben X._ (Beschwerdeführer) und seine Gattin Y._ (Beschwerdeführerin) Beschwerde in öffentlich-rechtlichen Angelegenheiten und beantragen dem Bundesgericht, das Urteil des Verwaltungsgerichts sei aufzuheben. Dem Beschwerdeführer sei eine Niederlassungsbewilligung, eventuell eine Aufenthaltsbewilligung zu erteilen und vom Widerruf der Aufenthaltsbewilligung der Beschwerdeführerin sei abzusehen; ihr und den Kindern sei der weitere Aufenthalt in der Schweiz zu gestatten. Die Beschwerdeführenden beantragen zudem die unentgeltliche Prozessführung und Verbeiständung. Mit Verfügung vom 16. November 2012 hat der Präsident der II. öffentlich-rechtlichen Abteilung der Beschwerde antragsgemäss aufschiebende Wirkung zuerkannt. Das Sicherheits- und Justizdepartement und das Verwaltungsgericht des Kantons St. Gallen wie auch das Bundesamt für Migration beantragen, die Beschwerde sei abzuweisen.