Sachverhalt: A. X._ (geb. 1964) ist kroatischer Staatsangehöriger. Er reiste 1988 in die Schweiz ein und heiratete eine in der Schweiz aufenthaltsberechtigte Serbin, worauf er ebenfalls eine Aufenthaltsbewilligung erhielt. Dem Ehepaar wurden in den Jahren 1988 und 1990 zwei Töchter geboren, im Dezember 1991 liess es sich scheiden. Die Ausländerbehörde weigerte sich in der Folge, die Aufenthaltsbewilligung von X._ zu verlängern. Sie begründete dies zum einen mit dem Ende der Ehe, zum andern hielt sie fest, er habe zu verschiedenen Klagen Anlass gegeben; namentlich bestünden Betreibungen und Verlustscheine in der Höhe von mehreren zehntausend Franken gegen hin. Angesichts der politischen Lage im ehemaligen Jugoslawien wurde X._ die Ausreisefrist indes mehrfach verlängert und später kam er in den Genuss einer Kurzaufenthaltsbewilligung. B. Im September 1997 heiratete X._ in Bosnien und Herzegowina seine jetzige Ehefrau, die, wie er, aus Kroation stammt und in der Schweiz über eine Niederlassungsbewilligung verfügt. Ein Gesuch um Familiennachzug verweigerte die Fremdenpolizei zunächst, dies zum einen wegen zahlreichen Verstössen gegen die Ausländergesetzgebung, die jeweils mit geringfügigen Bussen geahndet worden waren, zum andern wegen den Schulden von X._: Gegen ihn lagen Verlustscheine in der Höhe von Fr. 85'136.-- vor und es liefen Betreibungen über rund Fr. 45'000.--. Später zog die Fremdenpolizei ihren Entscheid in Wiedererwägung, dies unter der Bedingung, dass X._ eine ihm angebotene Stelle auch tatsächlich antrete und monatlich Fr. 1'300.-- seiner Schulden zurückzahle. C. Mit Strafbefehl vom 4. Juli 2008 sprach das Untersuchungsrichteramt St. Gallen X._ wegen Verfügung über mit Beschlag belegte Vermögenswerte schuldig und es verurteilte ihn zu einer Geldstrafe von 15 Tagessätzen in der Höhe von je Fr. 50.-- und zu einer Busse von Fr. 500.--; er hatte ein ihm gehörendes, aber gepfändetes und mit einem Veräusserungsverbot belegtes Motorfahrzeug verkauft. D. Am 18. März 2009 verwarnte das Ausländeramt (heute Migrationsamt) des Kantons St. Gallen X._ und wies ihn an, "sich künftig in jeder Beziehung klaglos zu verhalten (keine strafrechtlichen Verurteilungen mehr, keine neuen Schulden mehr und Tilgung der bestehenden Schulden) ". Zum damaligen Zeitpunkt bestanden Verlustscheine gegenüber X._ in der Höhe von insgesamt Fr. 312'170.75. Mit Verfügung vom 15. Juni 2011 weigerte sich das Migrationsamt des Kantons St. Gallen, die Aufenthaltsbewilligung von X._ erneut zu verlängern und wies ihn aus der Schweiz weg. Es begründete dies mit den strafrechtlichen Verurteilungen, seinen finanziellen Verhältnissen sowie der mangelnden Integration in den Arbeitsprozess. Diesen Entscheid bestätigten das Sicherheits- und Justizdepartement des Kantons St. Gallen mit Entscheid vom 4. Mai 2012 und das Verwaltungsgericht des Kantons St. Gallen mit Urteil vom 15. Oktober 2012. E. Gegen diesen Entscheid erhebt X._ (Beschwerdeführer) mit Eingabe vom 12. November 2012 beim Bundesgericht Beschwerde in öffentlich-rechtlichen Angelegenheiten. Er beantragt, das Urteil des Verwaltungsgerichts (Vorinstanz) sei aufzuheben und von einem Widerruf der Aufenthaltsbewilligung und einer Wegweisung sei abzusehen; eventuell sei ihm der weitere Aufenthalt in der Schweiz mit Auflagen und Bedingungen oder unter Annahme eines Härtefalls zu bewilligen. Sodann beantragt der Beschwerdeführer die unentgeltliche Rechtspflege. Die Vorinstanz, das Sicherheits- und Justizdepartement des Kantons St. Gallen sowie das Bundesamt für Migration beantragen die Abweisung der Beschwerde. Mit Verfügungen vom 16. November 2012 hat der Präsident der II. öffentlich-rechtlichen Abteilung des Bundesgerichts der Beschwerde die aufschiebende Wirkung zuerkannt und auf die Erhebung eines Kostenvorschusses verzichtet.