Faits : A. A.X._, ressortissant algérien né en 1970, est arrivé en Suisse le 1 er janvier 2011. Le 28 mai 2012, il a déposé une demande de mariage avec une ressortissante française, B.Y._, née en 1979 et titulaire d'une autorisation d'établissement UE/AELE. Le mariage a été célébré le 13 septembre 2013. Le 7 janvier 2014, une fille est issue de cette union, C.X._. L'épouse de l'intéressé attend un second enfant pour 2016. L'intéressé a obtenu une autorisation de séjour UE/AELE au titre du regroupement familial le 28 mars 2014. A.X._ est connu des autorités sous onze identités différentes, notamment utilisées pour séjourner en Suisse avant 2011. Depuis 2005, il a été condamné à huit reprises pour des infractions contre le patrimoine et contre l'autorité publique, ainsi que pour faux dans les titres, violation de domicile et multiples infractions à la législation sur les étrangers. Ses condamnations ont varié entre 45 jours et dix mois de peine privative de liberté. B. Par décision du 4 août 2015, le Service de la population du canton de Vaud (ci-après: le Service cantonal) a révoqué l'autorisation de séjour UE/AELE de A.X._ et a prononcé son renvoi de Suisse. L'intéressé a recouru contre ce prononcé auprès de la Cour de droit administratif et public du Tribunal cantonal du canton de Vaud (ci-après: le Tribunal cantonal) le 10 septembre 2015. Par arrêt du 18 mars 2016, le Tribunal cantonal a rejeté le recours de A.X._. Il a jugé en bref que celui-ci avait dissimulé des faits essentiels aux autorités, qu'il avait attenté de manière répétée à la sécurité et l'ordre publics en Suisse et, en lien avec ses infractions, qu'il présentait un risque de récidive élevé, concret et actuel, ce qui justifiait la révocation de l'autorisation de séjour UE/AELE. Le Tribunal cantonal a en outre considéré que la mesure prononcée respectait le principe de la proportionnalité. C. Agissant par la voie du recours en matière de droit public, A.X._, B.X._ et C.X._ demandent en substance au Tribunal fédéral, sous suite de frais et dépens, outre l'assistance judiciaire et l'effet suspensif, de réformer l'arrêt du 18 mars 2016 du Tribunal cantonal et de maintenir l'autorisation de séjour UE/AELE de A.X._; subsidiairement d'annuler l'arrêt précité et de renvoyer la cause à l'autorité précédente pour nouvelle décision dans le sens des considérants. Ils se plaignent de violation du droit fédéral et international. Par ordonnance du 14 avril 2016, 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 et le Service cantonal renoncent tous deux à se déterminer. Le Secrétariat d'Etat aux migrations conclut au rejet du recours.