Sachverhalt:
A.
A._ (1979, Pakistaner) heiratete am 24. September 2001 eine Schweizerin (1959), nachdem zuvor zwei Versuche, politisches Asyl zu erhalten, gescheitert waren. Am 21. Januar 2002 erhielt er nach Ausräumung des Verdachts auf eine "Gefälligkeitsehe" eine provisorische und am 27. März 2002 eine definitive Aufenthaltsbewilligung. Am 14. August 2006 erklärten die Eheleute, dass ihre eheliche Gemeinschaft intakt sei, gelebt werde und weder eine Trennung noch eine Scheidung geplant noch bereits erfolgt sei. In der Folge erhielt A._ eine Niederlassungsbewilligung (29. August 2006). Bereits zuvor, am 30. Mai 2006, beantragte er die erleichterte Einbürgerung. Im Rahmen des Einbürgerungsverfahrens erklärten die Eheleute wiederum, dass sie in einer stabilen, ungetrennten ehelichen Gemeinschaft lebten und weder Trennungs- noch Scheidungsabsichten bestünden. Am 19. März 2009 wurde A._ erleichtert eingebürgert.
Im Herbst 2009 verliess A._ die Schweiz und kehrte am 1. März 2011 zurück. Seine Ehe wurde am 17. Mai 2011 geschieden. Am 15. Oktober 2014 erklärte das - damals noch so bezeichnete - Bundesamt für Migration die erleichterte Einbürgerung entsprechend Art. 41 des nunmehr aufgehobenen Bürgerrechtsgesetzes vom 29. September 1952 (AS 1952 1087) als nichtig. Dieser Entscheid ist unangefochten rechtskräftig geworden.
B.
Am 1. September 2015 beantragte A._ beim Migrationsamt des Kantons Thurgau die Verlängerung der bestehenden Bewilligung. Nach Gewährung des rechtlichen Gehörs stellte dieses am 11. März 2016 fest, dass die Niederlassungsbewilligung gestützt auf Art. 61 Abs. 1 lit. a AuG von Gesetzes wegen erloschen sei. Sein Gesuch um Erneuerung der Niederlassungsbewilligung wurde abgewiesen. Die Rechtsmittel dagegen waren alle erfolglos (Entscheid des Departementes für Justiz und Sicherheit vom 12. August 2016; Entscheid des Verwaltungsgerichts vom 15. März 2017).
C.
Vor Bundesgericht beantragt A._, den Entscheid des Verwaltungsgerichts vom 15. März 2017 aufzuheben, die Angelegenheit zur Wiedererteilung der Niederlassungsbewilligung, evtl. der Aufenthaltsbewilligung und zur Neuregelung der bisherigen Verfahrenskosten an die Vorinstanz zurückzuweisen sowie keine Verfahrenskosten zu erheben.
D.
Das Migrationsamt, das Departement für Justiz und Sicherheit und das Verwaltungsgericht des Kantons Thurgau beantragen die Abweisung der Beschwerde. Der Beschwerdeführer hat sich dazu vernehmen lassen.
Mit Verfügung vom 29. Mai 2017 erteilte der Präsident der II. öffentlich-rechtlichen Abteilung des Bundesgerichts der Beschwerde aufschiebende Wirkung.

Erwägungen:
1.
Auf dem Gebiet des Ausländerrechts ist die Beschwerde in öffentlich-rechtlichen Angelegenheiten - wie hier - gegen die Feststellung des Erlöschens der Niederlassungsbewilligung zulässig (Urteil 2C_866/ 2017 vom 7. März 2018 E. 1.1; <ref-law> e contrario). Auch die weiteren Sachurteilsvoraussetzungen (Art. 42 Abs. 1, 2, Art. 82 lit. a, Art. 86 Abs. 1 lit. d, Art. 89 Abs. 1, Art. 90, Art. 100 Abs. 1 BGG) sind erfüllt, weshalb auf die Beschwerde einzutreten ist.
2.
2.1. Bevor der Beschwerdeführer das schweizerische Bürgerrecht erhielt, besass er eine Niederlassungsbewilligung. Mit der Nichtigerklärung des Schweizerbürgerrechts kommt ihm als Niedergelassenem entsprechend der bundesgerichtlichen Rechtsprechung wieder die gleiche Rechtsstellung wie vor der Einbürgerung zu (<ref-ruling> E. 3.7 S. 8). Vorbehalten bleiben die ausländerrechtlichen Erlöschens- und Widerrufsgründe (<ref-ruling> E. 3.7 S. 8; Urteil 2C_1115/2015 vom 20. Juli 2016 E. 3.2).
2.2. Die Vorinstanz hat die Niederlassungsbewilligung nicht widerrufen, sondern festgestellt, dass diese nach Art. 61 Abs. 1 lit. a und Abs. 2 AuG von Gesetzes wegen erloschen sei. Danach erlischt eine Niederlassungsbewilligung mit der Abmeldung ins Ausland (Abs. 1 lit. a) oder nach sechs Monaten, wenn der Ausländer ohne Abmeldung die Schweiz verlässt (Abs. 2 Satz 1). Auf Gesuch hin kann die Niederlassungsbewilligung während vier Jahren aufrechterhalten werden (Art. 61 Abs. 2 Satz 2 AuG).
Die Vorinstanz führt dazu aus, dass der Beschwerdeführer Ende 2009 die Schweiz endgültig verlassen habe. Dies ergebe sich zum einen daraus, dass er seine Arbeitsstelle gekündigt habe, und zum anderen auch aus den Aussagen seiner Exfrau und seines ehemaligen Arbeitgebers. Zudem habe er kein Verlängerungsgesuch nach Art. 61 Abs. 2 Satz 2 AuG gestellt.
2.3.
2.3.1. Das Schweizerbürgerrecht des Beschwerdeführers wurde am 15. Oktober 2014 als nichtig erklärt. Bis zu diesem Zeitpunkt war der Beschwerdeführer somit Schweizer Bürger: Mit der Erteilung des Schweizerbürgerrechts fällt die persönliche Eigenschaft als Ausländer dahin, selbst wenn damit eine doppelte Staatsangehörigkeit verbunden sein sollte. Ausländer ist nur, wer nicht über das Schweizerbürgerrecht verfügt (<ref-ruling> E. 3.4 i.i. S. 6). Insofern unterstand der Beschwerdeführer bis zum 15. Oktober 2014 nicht dem AuG.
2.3.2. Die Vorinstanz kommt in ihren Ausführungen trotzdem zum Schluss, dass das AuG anwendbar sei. Sie nimmt dabei Bezug auf <ref-ruling> E. 3.7 (S. 8), wonach dem Ausländer zwar die gleiche Rechtsstellung wie vor der Einbürgerung zuzuweisen sei. "Vorbehalten [blieben allerdings] inzwischen eingetretene Erlöschens- oder Widerrufsgründe nach Art. 9 Abs. 3 und 4 ANAG" (BS 1 121; Art. 9 Abs. 3 lit. c ANAG ≈ Art. 61 Abs. 1 lit. a und Abs. 2 AuG). Gestützt darauf führt die Vorinstanz deshalb aus, dass "der Beschwerdeführer ab 19. März 2009 (Zeitpunkt der für nichtig erklärten Einbürgerung) grundsätzlich über eine Niederlassungsbewilligung verfügt hätte". Die Vorinstanz geht damit davon aus, dass aus der Nichtigerklärung der Einbürgerung nicht nur die gleiche Rechtsstellung wie vor der Einbürgerung folgt, sondern gleichzeitig auch der Zeitpunkt, wann der Schweizer Bürger wieder in den Stand des niederlassungsberechtigten Ausländers fällt. Insofern ist sie ohne Begründung von einer ex tunc Wirkung ausgegangen, weshalb das AuG und die Erlöschensgründe rückwirkend wieder Anwendung finden.
2.3.3. Das Bundesgericht hat indes nur über den Rechtsstatus diskutiert. Es hat zudem bereits damals darauf hingewiesen, dass gewisse Wirkungen nicht behoben werden können (z.B. politische Rechte; <ref-ruling> E. 3.5 S. 7). Sodann verlangt Art. 61 Abs. 2 AuG eine ex nunc Wirkung: Nach dieser Bestimmung kann der Ausländer, wenn er die Schweiz verlässt, auf Gesuch hin seine Niederlassungsbewilligung verlängern. Wenn ein Schweizer Bürger nun rückwirkend auf den Zeitpunkt der Einbürgerung wieder Ausländer würde, im damaligen Zeitpunkt aber als Schweizer Bürger ins Ausland verreist war, konnte er kein Gesuch um Verlängerung einreichen. Damit würden seine gesetzlichen Rechte missachtet und ohne gesetzliche Grundlage (<ref-law>) auch seine ausländerrechtliche Stellung verschlechtert, was zum einen verfassungsrechtlich unzulässig ist und zum anderen das Bundesgericht in <ref-ruling> E. 3.6 und 3.7 S. 8 ausdrücklich ablehnte. Die gesetzlich vorgesehene Möglichkeit der Aufrechterhaltung der Niederlassungsbewilligung trotz Ausreise ins Ausland (Art. 61 Abs. 2 AuG) kann nicht rückwirkend geschaffen werden. Die Vergangenheit lässt sich nicht wieder herstellen. Insofern ist in diesem Fall nur eine Wirkung ex nunc möglich.
2.4. Zusammenfassend ist festzuhalten: Die Nichtigerklärung des Schweizerbürgerrechts entfaltet seine Wirkung erst ab dem Zeitpunkt der Nichtigerklärung (Wirkung ex nunc). Die von der Vorinstanz angeführten Bestimmungen des AuG sind demnach nicht anwendbar, weshalb die Niederlassungsbewilligung nicht erloschen ist. Daran ändert auch nichts, dass der Beschwerdeführer 2009 bösgläubig gewesen sein soll. Insofern ist <ref-ruling> zu präzisieren: Der Erlöschensgrund der mehr als sechsmonatigen Landesabwesenheit (Art. 61 Abs. 2 AuG) ist nicht anwendbar. Das damalige Urteil bezog sich auf die Rechtslage unter dem ANAG, das die Ausweisung (Art. 10 ANAG) als Erlöschensgrund vorsah (Art. 9 Abs. 3 lit. b ANAG).
2.5. Die Vorinstanz hat die Niederlassungsbewilligung nicht widerrufen. Offenbar sprechen keine Gründe dafür. Allerdings ist der Sachverhalt nicht derart erstellt, dass das Bundesgericht direkt darüber entscheiden kann, ob die massgeblichen Voraussetzungen eines Widerrufs einer Niederlassungsbewilligung nicht erfüllt sind. Die Angelegenheit ist daher an das Migrationsamt des Kantons Thurgau zurückzuweisen zu ergänzender Abklärung der tatsächlichen Umstände und zu neuem Entscheid in der Sache.
3.
Demnach erweist sich die Beschwerde als begründet und ist gutzuheissen. Der Entscheid des Verwaltungsgerichts des Kantons Thurgau vom 15. März 2017 ist aufzuheben und die Sache zu neuem Entscheid an das Migrationsamt des Kantons Thurgau zurückzuweisen. Bei diesem Verfahrensausgang sind keine Kosten zu erheben (<ref-law>). Hingegen hat der Kanton Thurgau den Beschwerdeführer für das bundesgerichtliche Verfahren angemessen zu entschädigen (<ref-law>). Zur Regelung der Kosten- und Entschädigungsfolgen des kantonalen Verfahrens ist die Sache an das Verwaltungsgericht zurückzuweisen.

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird gutgeheissen. Der Entscheid des Verwaltungsgerichts des Kantons Thurgau vom 15. März 2017 wird aufgehoben und die Sache zu neuem Entscheid an das Migrationsamt des Kantons Thurgau zurückgewiesen.
2.
Es werden keine Gerichtskosten erhoben.
3.
Der Kanton Thurgau hat dem Beschwerdeführer für das bundesgerichtliche Verfahren eine Parteientschädigung von Fr. 2'500.-- auszurichten.
4.
Zur Regelung des Kosten- und Entschädigungsfolgen des kantonalen Verfahrens wird die Sache an das Verwaltungsgericht zurückgewiesen.
5.
Dieses Urteil wird den Verfahrensbeteiligten, dem Verwaltungsgericht des Kantons Thurgau und dem Staatssekretariat für Migration schriftlich mitgeteilt.
Lausanne, 24. Mai 2018
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Seiler
Der Gerichtsschreiber: Errass