Sachverhalt: A. Am 8. April 2010 reiste der indische Staatsangehörige A._ (geb. 1987) zu Ausbildungszwecken in die Schweiz ein und erhielt vom Kanton Luzern eine Aufenthaltsbewilligung B. Am 13. September 2012 heiratete er in Dänemark die portugiesische Staatsangehörige B._ (geb. 1991), welche am 23. August 2012 in die Schweiz eingereist war. Sie erhielt vom Kanton Waadt eine Aufenthaltsbewilligung B EU/EFTA. A._ erhielt anschliessend aufgrund des Familiennachzugs ebenfalls eine bis am 26. Juli 2017 gültige Aufenthaltsbewilligung B EU/EFTA des Kantons Waadt. Das Ehepaar verlegte seinen Wohnsitz später in den Kanton Bern und schliesslich in den Kanton Uri. B. Mit Verfügung vom 22. April 2016 widerrief die Volkswirtschaftsdirektion des Kantons Uri, Abteilung Migration, per 15. Juni 2016 die Aufenthaltsbewilligung von A._, wies ihn aus der Schweiz weg und setzte ihm eine Ausreisefrist gleichen Datums. Als Begründung führte sie im Wesentlichen aus, es liege eine Scheinehe vor. Das Dispositiv lautete: "Widerruf Ihrer Aufenthaltsbewilligung B EG/EFTA per 15. Juni 2016 und Wegweisung aus der Schweiz per 15. Juni 2016 (Ausreisefrist); Antrag Einreiseverbot beim Staatssekretariat für Migration SEM." Die Kostenregelung (Die Kosten von Fr. 150.-- wurden A._ auferlegt) befand sich nicht im Dispositiv, sondern am Ende der Begründung der Verfügung, unmittelbar vor der Rechtsmittelbelehrung. Die dagegen erhobene Einsprache vom 23. Mai 2016 bei der Volkswirtschaftsdirektion des Kantons Uri, Amt für Arbeit und Migration, wurde mit Entscheid vom 2. September 2016 abgelehnt, wobei das Dispositiv wie folgt formuliert war: "1. Die Einsprache wird abgelehnt. 2. Sie haben die Schweiz bis Ende Oktober 2016 zu verlassen. 3. [Rechtsmittelbelehrung]." Anschliessend gelangte A._ mit Beschwerde an das Obergericht des Kantons Uri, welches diese mit Urteil vom 10. Februar 2017 abwies. C. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 13. März 2017 beantragt A._ (Beschwerdeführer) die Aufhebung des vorinstanzlichen Urteils und Erneuerung seiner Aufenthaltsbewilligung B EU/EFTA. Eventualiter sei das vorinstanzliche Urteil aufzuheben und die Vorinstanz anzuweisen, dass das Amt für Arbeit und Migration Uri formell korrekte Verfügungen zu erlassen habe. Die Vorinstanz erachtet in ihrer Vernehmlassung vom 20. März 2017 die formellen Rügen als unbegründet, während das Amt für Arbeit und Migration auf eine Vernehmlassung verzichtet hat. Mit Präsidialverfügung vom 15. März 2017 wurde der Beschwerde antragsgemäss die aufschiebende Wirkung zuerkannt.