Erwägungen:
1.
1.1. Der türkische Staatsangehörige X._ (geb. 1979) reiste am 22. November 2004 in die Schweiz ein, heiratete am 13. Dezember 2004 die Schweizer Bürgerin A._ (geb. 1970) und erhielt daraufhin eine letztmals bis 30. November 2011 verlängerte Aufenthaltsbewilligung.
Die Eheleute waren bis Ende Februar 2007 im Kanton Aargau wohnhaft. Am 21. Februar 2007 meldete sich X._ in Winterthur an, wobei er als künftigen Wohnort denjenigen seiner Ehefrau angab. Es handelte sich dabei um das "Motel B._", in dem die Familie "X._-A._" vom 1. März 2007 bis 18. Dezember 2007 ein Doppelzimmer für monatlich Fr. 1'200.-- gemietet hatte. Am 18. Dezember 2007 meldete sich X._ in Zürich als bei C._ wohnhaft an. Die Scheidung erfolgte am 8. Dezember 2008.
1.2. Mit Verfügung vom 12. Januar 2012 wies das Migrationsamt des Kantons Zürich das Gesuch von X._ um Verlängerung der Aufenthaltsbewilligung ab und wies ihn aus der Schweiz weg. Aus den Scheidungsakten ergebe sich, dass die eheliche Gemeinschaft bereits im Herbst 2006 aufgelöst worden sei. Die gegen die verweigerte Bewilligungsverlängerung erhobenen kantonalen Rechtsmittel blieben erfolglos.
1.3. Vor Bundesgericht beantragt X._, das Urteil des Verwaltungsgerichts des Kantons Zürich vom 31. Dezember 2012 aufzuheben und das Migrationsamt des Kantons Zürich anzuweisen, die Aufenthaltsbewilligung zu verlängern.
Das Verwaltungsgericht des Kantons Zürich verzichtet auf eine Vernehmlassung, die Sicherheitsdirektion des Kantons Zürich und das Bundesamt für Migration beantragen die Abweisung der Beschwerde.
1.4. Am 12. Februar 2013 hat der Abteilungspräsident der Beschwerde aufschiebende Wirkung zuerkannt.
2.
Die Beschwerde erweist sich als offensichtlich unbegründet, soweit sie überhaupt den gesetzlichen Begründungs- und Rügeanforderungen (Art. 42 Abs. 2 und Art. 106 Abs. 2 BGG) genügt; sie kann ohne Weiterungen mit summarischer Begründung im vereinfachten Verfahren nach Art. 109 BGG erledigt werden.
2.1. Der Beschwerdeführer beruft sich auf Art. 50 AuG (SR 142.20) und macht in vertretbarer Weise einen Bewilligungsanspruch geltend, weshalb die Beschwerde in öffentlich-rechtlichen Angelegenheiten zulässig ist (Art. 83 lit. c Ziff. 2 BGG e contrario; Urteil 2C_821/2011 vom 22. Juni 2012 E. 1, nicht publ. in: <ref-ruling>).
2.2. Strittig ist vorliegend der Zeitpunkt der Auflösung der ehelichen Gemeinschaft. Der Beschwerdeführer rügt eine offensichtlich unrichtige Sachverhaltsfeststellung der Vorinstanz (Art. 97 Abs. 1 BGG). Die eheliche Gemeinschaft sei nicht bereits - wie von der Vorinstanz festgestellt - im Herbst 2006, sondern erst im Februar 2008 aufgelöst worden. In der Folge sei ein Bewilligungsanspruch nach Art. 50 Abs. 1 lit. a AuG zu Unrecht verneint worden.
2.3. Das Bundesgericht legt seinem Urteil den von der Vorinstanz festgestellten Sachverhalt zugrunde (Art. 105 Abs. 1 BGG), es sei denn, dieser sei offensichtlich unrichtig oder beruhe auf einer Rechtsverletzung im Sinne von Art. 95 BGG (Art. 105 Abs. 2 BGG; <ref-ruling> E. 1.6 S. 280 f.; Urteil 2C_300/2013 vom 21. Juni 2013 E. 2.1). Die betroffene Person muss rechtsgenügend dartun, dass und inwiefern der festgestellte Sachverhalt in diesem Sinne mangelhaft erscheint und die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (Art. 97 Abs. 1 i.V.m. Art. 42 Abs. 2 und Art. 106 Abs. 2 BGG; vgl. <ref-ruling> E. 1.4.3 S. 254 f.; <ref-ruling> E. 1.3 S. 351 f.).
2.4. Gemäss Art. 50 Abs. 1 lit. a AuG besteht der Anspruch auf Verlängerung der Aufenthaltsbewilligung nach den Art. 42 und 43 AuG nach Auflösung der Ehe fort, wenn die Ehegemeinschaft mindestens drei Jahre bestanden und sich der ausländische Ehegatte erfolgreich integriert hat (<ref-ruling> E. 3.3.3 S. 119). Eine (relevante) Ehegemeinschaft liegt dabei solange vor, als die eheliche Beziehung tatsächlich gelebt wird und ein gegenseitiger Ehewille besteht (<ref-ruling> E. 2 S. 231; <ref-ruling> E. 3.1.2 S. 347). Im Regelfall ist auf die Dauer der nach aussen wahrnehmbaren ehelichen Wohngemeinschaft abzustellen (vgl. Art. 42 Abs. 1 bzw. Art. 43 Abs. 1 AuG und Art. 49 AuG). Davon ist namentlich dann abzuweichen, wenn aufgrund der besonderen Umstände des Einzelfalls davon auszugehen ist, dass nur mehr eine faktische Wohngemeinschaft vorliegt, d.h. die eheliche Beziehung trotz eines (fortdauernden) gemeinsamen Wohnsitzes nicht mehr gelebt wird und der Ehewille erloschen ist (vgl. z.B. Urteile 2C_690/2012 vom 15. Februar 2013 E. 3.2; 2C_366/2012 vom 1. Mai 2012 E. 2.2; 2C_786/2011 vom 23. Dezember 2011 E. 2.3; 2C_531/2011 vom 19. Dezember 2011 E. 2.3; 2C_904/2010 vom 27. April 2011 E. 2.3.1; 2C_544/2010 vom 23. Dezember 2010 E. 2.2).
2.5. Zur Bestimmung des Zeitpunkts der Auflösung der Ehegemeinschaft hat die Vorinstanz massgeblich auf die Aussagen des Beschwerdeführers und seiner vormaligen Ehefrau im Scheidungsverfahren abgestellt. Die Eheleute haben anlässlich der Anhörung vom 25. September 2008 übereinstimmend ausgeführt, dass sie seit September 2006 getrennt lebten. Angesichts dieser klaren und bestimmten Aussagen ist die Vorinstanz davon ausgegangen, ein allfälliges Zusammenwohnen der Beschwerdeführer seit 2006 sei nicht über eine faktische Wohngemeinschaft hinausgegangen.
2.6. Was der Beschwerdeführer dagegen vorbringt, lässt die vorinstanzliche Sachverhaltsfeststellung nicht als im Ergebnis willkürlich erscheinen. Zwar ist das von der Migrationsbehörde angestrengte Strafverfahren gegen den Beschwerdeführer (Vorwurf der Täuschung der Behörden gemäss Art. 118 AuG) nicht an die Hand genommen worden, doch hat die Staatsanwaltschaft ausdrücklich offengelassen, ob die eheliche Gemeinschaft ab dem 22. Februar 2007 noch gelebt worden sei. Der Bestätigung zur Miete eines Doppelzimmers im "Motel B._" lässt sich dazu ebenfalls nichts entnehmen. Was die Meldeverhältnisse betrifft, hat sich der Beschwerdeführer fünf Tage nach Ablauf der Dreijahresfrist i.S.v. Art. 50 Abs. 1 lit. a AuG in Zürich als bei C._ wohnhaft angemeldet. Sie war gemäss vorinstanzlicher Feststellung die neue (Lebens-) Partnerin des Beschwerdeführers. Dies wird von diesem zwar bestritten, ist jedoch angesichts dessen, dass er C._ in der Anhörung vom 25. September 2008 ausdrücklich als "Partnerin" bezeichnet hat, nicht offensichtlich unhaltbar, auch wenn der Beschwerdeführer nun ausführt, dass er damit die Wohnpartnerin und nicht die Lebenspartnerin gemeint habe. Schliesslich durfte die Vorinstanz davon ausgehen, dass die Beziehung bereits einige Zeit vor dem Zusammenziehen am 18. Dezember 2007 bestanden hatte.
2.7.
2.7.1. Soweit der Beschwerdeführer erstmals vor Bundesgericht ein Schreiben von C._ zur Art der persönlichen Beziehung zum Beschwerdeführer auflegt, ist er damit nicht zu hören. Abzustellen ist auf den Sachverhalt zum Zeitpunkt des vorinstanzlichen Entscheids; nachträglich eingetretene Tatsachen und entsprechende Beweismittel ("echte Noven") bleiben im bundesgerichtlichen Verfahren in jedem Fall unberücksichtigt (Art. 99 Abs. 1 BGG; <ref-ruling> E. 3.5 S. 397; <ref-ruling> E. 5.2.4 S. 229; <ref-ruling> E. 2.1 S. 343 f.; Urteile 2C_906/2012 vom 5. Juni 2013 E. 1.4; 8C_928/2012 vom 26. April 2013 E. 5). Die ausnahmsweise Zulassung neuer Vorbringen nach Art. 99 Abs. 1 BGG bezieht sich auf Tatsachen und Beweismittel, die erst durch das angefochtene Urteil rechtserheblich werden; unzulässig sind hingegen Vorbringen, die bereits der Vorinstanz hätten vorgebracht bzw. vorgelegt werden können (<ref-ruling> E. 4.4.3 S. 128 f.; Urteil 2C_856/2012 vom 25. März 2013 E. 2.3 mit Hinweis).
2.7.2. Letzteres trifft vorliegend zu: Der Beschwerdeführer musste damit rechnen, dass sich die Vorinstanz zur vorliegend strittigen Frage des Zeitpunkts der Auflösung der ehelichen Gemeinschaft auch auf die in den Akten befindlichen Hinweise zu einer allfälligen neuen Beziehung des Beschwerdeführers stützt und diese entsprechend würdigt. Es wäre dem Beschwerdeführer daher möglich und zumutbar gewesen, sich bereits vor der Vorinstanz näher zur Art der persönlichen Beziehung zu C._ zu äussern. Eine Verletzung des rechtlichen Gehörs (Art. 29 Abs. 2 BV) durch eine völlig überraschende rechtliche Würdigung bringt der Beschwerdeführer denn auch zu Recht nicht vor (<ref-ruling> E. 2c/aa S. 22; Urteil 2C_578/2012 vom 22. Februar 2013 E. 2.2 mit Hinweisen).
2.8. Weitere, zulässige Indizien bzw. Beweismittel für eine Ehegemeinschaft in der Zeit vom 1. März 2007 bis 18. Dezember 2007 (z.B. Aussagen der vormaligen Ehefrau und Dritter) vermochte der Beschwerdeführer - wie er selbst einräumt - im vorinstanzlichen Verfahren nicht vorzubringen. Dasselbe gilt für die von ihm behauptete Beziehung, die er ab Juli 2008 mit einer namentlich nicht genannten Person geführt haben will.
2.9. Ein Verstoss gegen Treu und Glauben (Art. 9 BV) seitens der Migrationsbehörde liegt nicht vor. Wenn diese den Sachverhalt bei den vorangegangenen Bewilligungsverlängerungen nicht näher abgeklärt und auf einen Beizug der Scheidungsakten verzichtet hat, ist dies massgeblich auf die bei der ersten Bewilligungsverlängerung nach der Aufhebung der ehelichen Gemeinschaft gemachten Angaben des Beschwerdeführers zurückzuführen, wonach die eheliche Gemeinschaft bis Februar 2008 und damit über drei Jahre gedauert habe. Dies erwies sich bei näherer Prüfung als falsch, was nicht der Migrationsbehörde, sondern dem Beschwerdeführer anzulasten ist (vgl. Urteil 2C_658/2011 vom 20. Januar 2012 E. 3.3). Ausserdem begründet die blosse Erneuerung einer Aufenthaltsbewilligung für sich allein noch kein schutzwürdiges Vertrauen auf weitere Verlängerungen derselben (<ref-ruling> E. 3b S. 388; Urteile 2C_40/2012 vom 15. Oktober 2012 E. 5; 2C_77/2011 vom 25. Mai 2011 E. 3.3).
2.10. Aus den genannten Gründen ist die vorinstanzliche Sachverhaltsfeststellung nicht zu beanstanden und ein Verstoss gegen Treu und Glauben zu verneinen. Zusätzliche Rügen erhebt der Beschwerdeführer nicht. Für alles Weitere kann daher auf die zutreffenden Ausführungen im vorinstanzlichen Urteil verwiesen werden (Art. 109 Abs. 3 BGG).
3.
Die Beschwerde ist abzuweisen. Dem Verfahrensausgang entsprechend wird der unterliegende Beschwerdeführer kostenpflichtig (Art. 66 BGG). Es sind keine Parteientschädigungen geschuldet (Art. 68 BGG).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen.
2.
Die Gerichtskosten von Fr. 1'000.-- werden dem Beschwerdeführer auferlegt.
3.
Dieses Urteil wird den Verfahrensbeteiligten, dem Verwaltungsgericht des Kantons Zürich, 4. Kammer, und dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 23. Juli 2013
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Zünd
Der Gerichtsschreiber: Egli