Sachverhalt: A. A._ (geb. 1974) ist serbischer Staatsangehöriger. Im Jahr 1991 erhielt er unter seinem früheren Namen "A._" eine Aufenthaltsbewilligung zum Verbleib bei seiner Ehefrau. Aus dieser Ehe ging eine Tochter (geb. 1993) hervor. Die Ehe wurde 1995 geschieden und die Tochter unter die elterliche Gewalt der Mutter gestellt. Mit Verfügung vom 31. Mai 1995 wies die damalige Fremdenpolizei des Kantons Zürich (heute Migrationsamt des Kantons Zürich, hiernach: Migrationsamt) das Gesuch von A._ um Verlängerung seiner Aufenthaltsbewilligung ab. Am 2. August 1996 wurde er ausgeschafft. Ein im Jahr 2006 von A._ gestelltes Gesuch um Erteilung einer Aufenthaltsbewilligung wurde am 31. Januar 2007 abgewiesen. Im Jahr 2009 stellte A._ ein erneutes Gesuch um Erteilung einer Aufenthaltsbewilligung. Im April 2010 reiste er ohne Visum in die Schweiz ein und erneuerte sein Gesuch. Mit Verfügung vom 5. Januar 2012 wies ihn das Migrationsamt aus dem Schengen-Raum weg. Das damalige Bundesamt für Migration (heute Staatssekretariat für Migration SEM) verfügte am 6. Januar 2012 gegen ihn ein bis zum 5. Januar 2017 gültiges Einreiseverbot. Am 7. Januar 2012 wurde er nach Serbien ausgeschafft. In der Folge hielt er sich trotz Einreiseverbot unter seinem neuen Namen "A._" immer wieder in der Schweiz auf und wurde erneut am 23. Juni 2014 ausgeschafft. Am 1. September 2014 heiratete er in seinem Heimatland die 1958 geborene und in der Schweiz niedergelassene österreichische Staatsangehörige B._. Am 22. September 2014 ersuchte diese um eine Einreisebewilligung für ihren Ehemann. Letzterer ersuchte selbst um eine Einreisebewilligung am 5. Februar 2015. Am 29. September 2015 reiste A._ erneut unbewilligt in die Schweiz ein. B. Mit Verfügung vom 16. Dezember 2015 wies das Migrationsamt die Gesuche vom 22. September 2014 und vom 5. Februar 2015 mit der Begründung ab, es liege eine Scheinehe vor. Ein Rekurs bei der Sicherheitsdirektion blieb erfolglos (Entscheid vom 21. Juni 2016). Die dagegen erhobene Beschwerde wies das Verwaltungsgericht des Kantons Zürich mit Urteil vom 2. Oktober 2016 ebenfalls ab. C. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 7. November 2016 beantragt A._ die Aufhebung des vorinstanzlichen Urteils. Es sei ihm eine Aufenthaltsbewilligung zu erteilen. Eventualiter sei die Angelegenheit zur Neubeurteilung an die Vorinstanz zurückzuweisen. Zudem beantragt er die unentgeltliche Rechtspflege im bundesgerichtlichen Verfahren. Mit Verfügung vom 11. November 2016 wurde das Gesuch um unentgeltliche Rechtspflege und Verbeiständung abgewiesen. Gleichentags wurde der Beschwerde antragsgemäss aufschiebende Wirkung zuerkannt. Sowohl die Vorinstanzen als auch das Staatssekretariat für Migration SEM verzichten auf Vernehmlassung.