Faits : A. X._, ressortissant portugais né en 1992, est entré en Suisse le 2 juin 2001 pour y rejoindre son oncle et sa tante. Il a été mis au bénéfice d'une autorisation d'établissement UE/AELE. Suite à des maltraitances dans sa famille, il a été placé dans un centre d'accueil et d'éducation spécialisée le 3 septembre 2004. Jusqu'en 2009, il a visité différents établissements afin notamment d'obtenir une formation, toutefois sans succès. Il a ensuite été placé sous tutelle, auprès d'une famille d'accueil, en mars 2010. Il a achevé une formation de plâtrier-peintre le 20 septembre 2011. Depuis le 1 er mars 2013, il est en suivi thérapeutique auprès d'une psychologue. Le 19 janvier 2015, l'intéressé s'est marié avec une ressortissante suisse née en 1996. Au 16 décembre 2014, l'intéressé était aux poursuites pour 1'666 fr. et faisait l'objet d'actes de défaut de biens pour un montant total de 31'484 fr. Au 21 janvier 2015, il émargeait en outre à l'assistance sociale pour un montant de 49'041 fr. X._ a fait l'objet de plusieurs condamnations. En tant que mineur, il a été condamné à trois reprises avec sursis à des peines d'un mois, 90 jours et 30 jours pour des infractions multiples, en particulier contre l'intégrité corporelle, le patrimoine et l'honneur ainsi que pour des infractions à la LStup (RS 812.121). En tant qu'adulte, il a été condamné à deux reprises, une première fois à une peine privative de liberté ferme de dix jours et une seconde fois à une peine privative de liberté ferme de 30 mois, cumulée à une peine pécuniaire de cinq jours-amende à 50 fr. chacun et à une amende de 1'000 fr. pour voies de fait, agression, vol, vol d'importance mineure, dommages à la propriété, injure, menaces, violation de l'art. 19a LStup et infraction qualifiée à la LStup. B. Par décision du 26 janvier 2015, le Service de la population et des migrations du canton du Valais (ci-après: le Service cantonal) a révoqué l'autorisation d'établissement de l'intéressé et ordonné son renvoi de Suisse pour le 28 février 2015. X._ a formé recours contre cette décision auprès du Conseil d'Etat du canton du Valais. Celui-ci a rejeté le recours par décision du 12 août 2015. Le 17 septembre 2015, l'intéressé a contesté ce prononcé auprès de la Cour de droit public du Tribunal cantonal du canton du Valais (ci-après: le Tribunal cantonal). Par arrêt du 6 novembre 2015, le Tribunal cantonal a rejeté le recours de X._. Il a jugé en bref que les conditions permettant la révocation de l'autorisation d'établissement étaient réunies, que l'intéressé présentait un risque de récidive et que la mesure était proportionnée. C. Agissant par la voie du recours en matière de droit public, X._ demande au Tribunal fédéral, sous suite de frais et dépens, outre l'effet suspensif, d'annuler l'arrêt du 6 novembre 2015 du Tribunal cantonal et de maintenir son autorisation d'établissement; subsidiairement d'annuler l'arrêt précité et de renvoyer la cause au Service cantonal pour instruction complémentaire et nouvelle décision. Il se plaint de violation du droit fédéral et, à tout le moins implicitement, du droit international. Par ordonnance du 14 décembre 2015, le Président de la IIe Cour de droit public du Tribunal fédéral a admis la demande d'effet suspensif. Le Tribunal cantonal renonce à se déterminer. Le Conseil d'Etat du canton du Valais et le Secrétariat d'Etat aux migrations concluent tous deux au rejet du recours. Dans des observations finales, X._ a confirmé ses conclusions.