Faits: A. A.X._, ressortissant du Yémen né en 1970, est arrivé en Suisse le 11 janvier 2004. Il y a obtenu l'asile le 15 décembre 2004. Son épouse, B.X._, ressortissante du Yémen née en 1970, est elle entrée en Suisse le 11 mai 2005. Comme ses enfants, C._, né en 1999, D._, née en 2001, et E._, né en 2006, A.X._ est actuellement au bénéfice d'une autorisation d'établissement délivrée par le canton du Valais valable jusqu'au 30 janvier 2014. Son épouse était titulaire d'une autorisation de séjour également délivrée par le canton du Valais et valable jusqu'au 11 janvier 2011. A.X._ et sa famille ont déposé le 19 février 2010, une demande de changement de canton pour aller s'installer dans le canton de Vaud. Ils ont emménagé le 1er mars 2010 dans un appartement situé à Clarens. Durant la procédure devant le Service de la population du canton de Vaud (ci-après: le Service de la population), A.X._ a précisé qu'il était en voie d'obtenir un diplôme d'une école hôtelière et qu'il recherchait activement une place de travail sur la Riviera vaudoise et ailleurs. Il a, notamment, produit une copie du procès-verbal d'un entretien avec son conseiller de l'Office régional de placement de Monthey-St Maurice (ci-après: l'ORP de Monthey) qui mentionnait qu'il serait plus facile pour l'intéressé de trouver un emploi sur la Riviera Vaudoise, à Lausanne ou à Genève. A.X._ a produit des copies de différents contrats de travail de durée déterminée. Le Centre social régional de Montreux a indiqué que le montant total des prestations versées à A.X._ au titre de revenu d'insertion du 1er mars au 31 juillet 2010 se montait à 19'916.70 fr. Par décision du 24 septembre 2010, le Service de la population a refusé d'autoriser le changement de canton en faveur de A.X._ et de sa famille, subsidiairement de transformer l'autorisation de séjour de son épouse en autorisation d'établissement. Il a justifié sa décision par le fait que les intéressés bénéficiaient des prestations de l'assistance publique depuis leur arrivée dans le canton de Vaud. Il leur a imparti un délai d'un mois pour quitter le canton de Vaud. B. A.X._ a recouru contre cette décision devant la Cour de droit administratif et public du Tribunal cantonal du canton de Vaud (ci-après: le Tribunal cantonal) et conclu à l'annulation de la décision du Service de la population "refusant le changement de canton au recourant et à sa famille". Il a fait valoir qu'il devait terminer ses études fin décembre 2010, mais qu'il était tenu d'effectuer des stages pour obtenir ses diplômes. Il a précisé que l'ORP de Monthey avait constaté qu'après six mois de recherche, il n'avait toujours pas trouvé de travail et que, sur conseil de l'ORP, il avait alors décidé de changer de canton. Il avait, ainsi, pu trouver des emplois de durée limitée. Il a ajouté que son nouvel employeur souhaitait l'engager à 100% une fois sa formation achevée fin avril 2011, produisant une lettre de la société confirmant ce fait. Dès la fin du mois d'avril 2011, il ne serait plus à l'assistance publique. Il a également précisé que ses enfants étaient scolarisés à Montreux. Par arrêt du 4 mars 2011, le Tribunal cantonal a rejeté le recours de A.X._. Il a en substance retenu que le recourant et sa famille, bénéficiaires de l'aide sociale en Valais, avaient également dû recourir à cette aide depuis leur arrivée dans le canton de Vaud, même pendant les périodes où le recourant travaillait. Cette situation n'était pas près de s'améliorer, puisque le salaire que le recourant devait obtenir depuis mars 2011, soit 1'770 fr. net par mois pour un travail à 50%, ne suffirait pas à l'entretien de sa famille; et ce même si le recourant parvenait à augmenter son taux de travail à 100%. Le Tribunal cantonal a ensuite estimé, "sous l'angle de la proportionnalité", qu'un retour dans le canton du Valais ne devait pas poser de problèmes. C. Agissant par la voie du recours constitutionnel subsidiaire, A.X._ demande au Tribunal fédéral, sous suite de frais et dépens, d'annuler l'arrêt du 4 mars 2011 du Tribunal cantonal et de l'autoriser à s'établir dans le canton de Vaud, subsidiairement, d'annuler l'arrêt attaqué et de renvoyer la cause au Tribunal cantonal pour une nouvelle décision dans le sens des considérants. Il invoque une violation arbitraire du droit de changer de canton. L'effet suspensif a été octroyé par décision présidentielle du 6 avril 2011. Le Service de la population et le Tribunal cantonal ont renoncé à se prononcer. 