Sachverhalt: A. X._ (geb. 1978) stammt aus Nigeria. 1999 und erneut 2001 reiste er in die Schweiz ein und suchte beide Male erfolglos um Asyl nach. In der Folge lebte er offenbar illegal in der Schweiz. Seit seiner Heirat mit einer Schweizerin im Februar 2006 ist er im Besitze einer Aufenthaltsbewilligung. Im Februar 2011 ersuchte X._ um Erteilung der Niederlassungsbewilligung, worauf ihm das Migrationsamt des Kantons Thurgau stattdessen mit Verfügung vom 28. Februar 2011 die Aufenthaltsbewilligung um ein Jahr verlängerte. Dieser Entscheid blieb unangefochten. Im Sommer 2011 trennte sich seine Schweizer Gattin von X._ und erklärte dabei, sie habe dies eigentlich schon seit Mitte 2010 vorgehabt, mit diesem Schritt aber zugewartet, bis die Fünfjahresfrist für den Erteilung der Niederlassungsbewilligung abgelaufen gewesen sei. B. Mit Verfügung vom 30. April 2012 verweigerte das Migrationsamt eine weitere Verlängerung der Aufenthaltsbewilligung von X._ und ordnete dessen Wegweisung an. Die kantonalen Rechtsmittel gegen diesen Entscheid blieben erfolglos; mit Urteil vom 13. Februar 2013 wies das Verwaltungsgericht des Kantons Thurgau kantonal letztinstanzlich eine Beschwerde von X._ ab. C. Gegen diesen Entscheid führt X._ am 5. April 2013 Beschwerde in öffentlich-rechtlichen Angelegenheiten beim Bundesgericht und beantragt im Wesentlichen die Erteilung der Niederlassungsbewilligung, eventuell die Verlängerung seiner Aufenthaltsbewilligung. Das Bundesamt für Migration, das Verwaltungsgericht und das Departement für Justiz und Sicherheit des Kantons Thurgau beantragen die Abweisung der Beschwerde. Das Migrationsamt des Kantons Thurgau stellt den Antrag, die Beschwerde sei abzuweisen, soweit darauf einzutreten sei. Mit Verfügung vom 11. April 2013 hat der Präsident der II. öffentlich-rechtlichen Abteilung des Bundesgerichts der Beschwerde antragsgemäss aufschiebende Wirkung zuerkannt.