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.

Considérant en droit :
1.
Le Tribunal fédéral examine d'office sa compétence (<ref-law>) et contrôle librement la recevabilité des recours qui lui sont soumis (<ref-ruling> consid. 2 p. 60; <ref-ruling> consid. 1 p. 133).
1.1. D'après l'art. 83 let. c ch. 2 LTF, le recours en matière de droit public est irrecevable contre les décisions relatives à une autorisation de droit des étrangers à laquelle ni le droit fédéral ni le droit international ne donnent droit. Selon la jurisprudence, il suffit, sous l'angle de la recevabilité, qu'il existe un droit potentiel à l'autorisation, étayé par une motivation soutenable, pour que cette clause d'exclusion ne s'applique pas et que, partant, la voie du recours en matière de droit public soit ouverte (cf. <ref-ruling> consid. 2.5 p. 315; arrêt 2C_587/2013 du 30 octobre 2013 consid. 1.1).
Le droit de séjour et d'accès à une activité économique est accordé aux ressortissants d'un Etat membre de la Communauté européenne conformément à l'ALCP (RS 0.142.112.681), dont les dispositions sont directement applicables (cf. <ref-ruling> consid. 2 p. 13; arrêt 2C_1061/2013 du 14 juillet 2015 consid. 1.2). Dans cette mesure, le motif d'irrecevabilité prévu à l'art. 83 let. c ch. 2 LTF ne leur est en principe pas opposable s'ils recourent contre une décision leur refusant le droit de séjourner en Suisse, sans toutefois que cela ne préjuge de l'issue du litige au fond (cf. <ref-ruling> consid. 1.2 p. 343 s.; arrêt 2C_587/2013 du 30 octobre 2013 consid. 1.2).
La recourante 2 est de nationalité française et bénéficie d'une autorisation UE/AELE (les juges cantonaux faisant indistinctement référence à une autorisation d'établissement dans la partie en fait de leur arrêt [consid. A], puis à une autorisation de séjour dans la partie en droit [consid. 2]). En tant que membre de la famille d'une ressortissante d'un Etat contractant, son époux, le recourant 1, peut tirer un droit au regroupement en Suisse au sens de l'<ref-law>. Il s'ensuit que le recourant 1 a droit à l'octroi ou au renouvellement d'une autorisation de séjour UE/AELE. Il invoque en outre également de manière soutenable une violation de l'art. 8 CEDH (cf. <ref-ruling> consid. 1d/aa p. 64 s.), de sorte que le présent recours n'entre pas dans les motifs d'exclusion de l'art. 83 let. c ch. 2 LTF et que la voie du recours en matière de droit public est ouverte.
1.2. Aux termes de l'<ref-law>, a qualité pour former un recours en matière de droit public quiconque a pris part à la procédure devant l'autorité précédente ou a été privé de la possibilité de le faire (let. a); est particulièrement atteint par la décision ou l'acte normatif attaqué (let. b); et a un intérêt digne de protection à son annulation ou à sa modification (let. c).
En l'occurrence, si le recourant 1, destinataire de l'arrêt attaqué ayant un intérêt digne de protection à son annulation ou à sa modification, a la qualité pour recourir devant le Tribunal fédéral, il n'en va toutefois pas de même des recourantes 2 et 3. Celles-ci n'ont en effet pas pris part à la procédure devant l'autorité précédente et n'ont en l'espèce aucunement expliqué en quoi elles auraient été privées de la possibilité de le faire (cf. <ref-ruling> consid. 2.2.3 p. 48; cf. FLORENCE AUBRY GIRARDIN, in Commentaire de la LTF, CORBOZ ET AL. [éd.], 2e éd. 2014, n° 21 s. ad <ref-law>). Par conséquent, le recours est irrecevable en tant qu'il concerne les recourantes 2 et 3.
1.3. Pour le surplus, s'agissant du recourant 1, le présent recours a été déposé en temps utile (<ref-law>) et dans les formes prescrites par la loi (<ref-law>). Il est en outre dirigé contre une décision rendue par une autorité cantonale supérieure de dernière instance (art. 86 al. 1 let. d et al. 2 LTF) dans une cause de droit public (<ref-law>), raison pour lesquelles il est recevable.
2.
Le Tribunal fédéral applique le droit d'office (<ref-law>). Il statue sur la base des faits établis par l'autorité précédente (cf. <ref-law>). Le recours ne peut critiquer les constatations de fait que si les faits ont été établis de façon manifestement inexacte ou en violation du droit au sens de l'<ref-law>, et si la correction du vice est susceptible d'influer sur le sort de la cause (<ref-law>), ce que la partie recourante doit démontrer d'une manière circonstanciée, conformément aux exigences de motivation de l'<ref-law> (cf. <ref-ruling> consid. 1.4.3 p. 254 s.). La notion de "manifestement inexacte" correspond à celle d'arbitraire au sens de l'art. 9 Cst. (<ref-ruling> consid. 2.1 p. 450).
3.
Le litige porte sur le point de savoir si, compte tenu des condamnations pénales que le recourant a subies depuis son arrivée en Suisse et des informations erronées données par celui-ci aux autorités quant à son identité, la révocation de l'autorisation de séjour UE/AELE est conforme au droit. Le recourant conteste en substance l'existence d'un risque de récidive caractérisé et le résultat de l'examen de la proportionnalité effectué par le Tribunal cantonal. Il se prévaut en particulier d'un cadre de vie stabilisé, de son mariage avec une ressortissante française, de la présence de sa fille en Suisse, ainsi que des répercussions d'un retour forcé en Algérie sur sa vie privée et familiale.
4.
4.1. La LEtr (RS 142.20) ne s'applique aux ressortissants des Etats membres de l'Union européenne que lorsque l'ALCP, dans sa version actuelle, n'en dispose pas autrement ou lorsqu'elle prévoit des dispositions plus favorables (art. 2 al. 2 LEtr). Comme l'ALCP ne réglemente pas la révocation de l'autorisation de séjour UE/AELE, c'est l'art. 62 LEtr qui est applicable (cf. art. 23 al. 1 de l'ordonnance fédérale du 22 mai 2002 sur l'introduction progressive de la libre circulation des personnes entre, d'une part, la Confédération suisse et, d'autre part, l'Union européenne et ses Etats membres, ainsi qu'entre les Etats membres de l'Association européenne de libre-échange [OLCP; RS 142.203]; arrêt 2C_370/2012 du 29 octobre 2012 consid. 3.1).
4.2. Aux termes de l'art. 62 let. a LEtr, l'autorisation de séjour peut être révoquée si l'étranger ou son représentant légal a fait de fausses déclarations ou a dissimulé des faits essentiels durant la procédure d'autorisation. Ainsi, lorsque l'autorité pose des questions à l'étranger, celui-ci doit y répondre conformément à la vérité. Les fausses déclarations, qui portent sur des élément déterminants pour l'octroi de l'autorisation de séjour ou d'établissement, conduisent à la révocation de celle-ci. Il ne doit toutefois pas être établi que l'autorisation aurait avec certitude été refusée si l'autorité avait obtenu une information correcte. Quant à la dissimulation de faits essentiels, au même titre que pour les fausses déclarations, il faut que l'étranger ait la volonté de tromper l'autorité. Cela est notamment le cas lorsqu'il cherche à provoquer, respectivement à maintenir, une fausse apparence sur un fait essentiel (arrêt 2C_706/2015 du 24 mai 2016 consid. 3.1 et les références citées, destiné à la publication).
4.3. Dans l'arrêt entrepris, le Tribunal cantonal a retenu que le 28 mai 2012, lorsqu'il a sollicité une autorisation de séjour en vue de son mariage, le recourant n'a pas mentionné avoir déjà fait l'objet de six condamnations pénales. Ce dernier ne conteste d'ailleurs pas ne pas avoir signalé ces infractions, relevant cependant que celles-ci n'étaient que de peu de gravité et principalement en lien avec le droit des étrangers.
En l'espèce, le recourant a tu des faits extrêmement importants pour apprécier son droit à l'octroi d'une autorisation de séjour, à savoir les condamnations pénales dont il avait précédemment fait l'objet en Suisse sous de fausses identités. Au moment de l'octroi de l'autorisation, l'autorité compétente aurait dû connaître ces faits afin, par exemple, de déterminer si le recourant portait atteinte à la sécurité et l'ordre public au sens de l'art. 62 let. c LEtr (cf. consid. 4.4 ci-dessous). Le cas échéant, elle aurait pu lui refuser l'octroi de l'autorisation demandée. La dissimulation de tels faits suffit ainsi à mettre en oeuvre le motif de révocation d'autorisation de l'<ref-law> (arrêt 2C_651/2009 du 1er mars 2010 consid. 4.1.1).
4.4. Il y a atteinte à la sécurité et à l'ordre publics, au sens des art. 62 let. c LEtr et 80 al. 1 let. a de l'ordonnance fédérale du 24 octobre 2007 relative à l'admission, au séjour et à l'exercice d'une activité lucrative (OASA; RS 142.201), notamment en cas de violation importante ou répétée de prescriptions légales ou de décisions d'autorité. Tel est aussi le cas lorsque les actes individuels ne justifient pas en eux-mêmes une révocation mais que leur répétition montre que la personne concernée n'est pas prête à se conformer à l'ordre en vigueur (arrêts 2C_797/2014 du 13 février 2015 consid. 3.3; 2C_977/2012 du 15 mars 2013 consid. 3.4; 2C_915/2010 du 4 mai 2011 consid. 3.2.1). En l'occurrence, le recourant a fait l'objet de huit condamnations, notamment pour des vols et des délits contre la législation sur les étrangers. Certes, ces condamnations ne sanctionnent pas des actes d'une gravité extrême. La multiplication des infractions commises sur une période de huit ans permet cependant de conclure que le recourant a attenté de manière répétée à la sécurité et à l'ordre publics en Suisse.
4.5. Il s'ensuit que le recourant réunit plusieurs motifs, au sens de l'art. 62 LEtr, qui constituent chacun une cause de révocation d'une autorisation de séjour.
5.
5.1. Comme l'ensemble des droits octroyés par l'ALCP, le droit de demeurer en Suisse ne peut être limité que par des mesures d'ordre ou de sécurité publics, au sens de l'<ref-law> (cf. <ref-ruling> consid. 5.3 p. 125 s.).
Conformément à la jurisprudence rendue en rapport avec l'<ref-law>, les limites posées au principe de la libre circulation des personnes doivent s'interpréter de manière restrictive. Ainsi, le recours par une autorité nationale à la notion d'"ordre public" pour restreindre cette liberté suppose, en dehors du trouble de l'ordre social que constitue toute infraction à la loi, l'existence d'une menace réelle et d'une certaine gravité affectant un intérêt fondamental de la société (<ref-ruling> consid. 5.3 p. 125 s. et les références citées). Il faut procéder à une appréciation spécifique du cas, portée sous l'angle des intérêts inhérents à la sauvegarde de l'ordre public, qui ne coïncide pas obligatoirement avec les appréciations à l'origine des condamnations pénales. Autrement dit, ces dernières ne sont déterminantes que si les circonstances les entourant laissent apparaître l'existence d'une menace actuelle et réelle, d'une certaine gravité pour l'ordre public (cf. <ref-ruling> consid. 5.3 p. 125 s. et les références citées). Il n'est pas nécessaire d'établir avec certitude que l'étranger commettra d'autres infractions à l'avenir pour prendre une mesure d'éloignement à son encontre; inversement, ce serait aller trop loin que d'exiger que le risque de récidive soit nul pour que l'on renonce à une telle mesure. En réalité, ce risque ne doit pas être admis trop facilement et il faut l'apprécier en fonction de l'ensemble des circonstances du cas, en particulier au regard de la nature et de l'importance du bien juridique menacé, ainsi que de la gravité de l'atteinte qui pourrait y être portée. L'évaluation de ce risque sera d'autant plus rigoureuse que le bien juridique menacé est important (<ref-ruling> consid. 5.3 p. 125 s. et les références citées). A cet égard, le Tribunal fédéral se montre particulièrement rigoureux, en lien avec l'<ref-law>, en présence d'infractions à la législation fédérale sur les stupéfiants, d'actes de violence criminelle et d'infractions contre l'intégrité sexuelle (cf. <ref-ruling> consid. 5.3 p. 125 s.; <ref-ruling> consid. 3.3 p. 303 s.; arrêt 2C_862/2012 du 12 mars 2013 consid. 3.1).
5.2. En l'occurrence, le recourant a été condamné à huit reprises, à des peines oscillant entre 45 jours et dix mois de peine privative de liberté. Ses condamnations ont toutefois exclusivement porté sur des infractions contre le patrimoine (vol, dommage à la propriété, escroquerie, utilisation frauduleuse d'un ordinateur), contre l'autorité publique (rupture de ban), contre la liberté (violation de domicile), ainsi que pour faux dans les titres et pour séjour illégal (au sens de l'ancienne loi fédérale du 26 mars 1931 sur le séjour et l'établissement des étrangers [aLSEE; RO 49 279] et de la LEtr). Depuis son mariage, le recourant n'a toutefois plus commis d'infractions (il a en revanche été condamné à 45 jours de peine privative de liberté pour des faits antérieurs; <ref-law>).
On constate donc en premier lieu que le recourant n'a jamais été condamné pour des infractions envers lesquelles le Tribunal fédéral se montre particulièrement rigoureux. Même si le rythme moyen d'une condamnation par année est certes élevé, on doit retenir que depuis son mariage et la naissance de sa fille en 2013, respectivement 2014, le recourant n'a plus commis d'infractions. Le risque de récidive, compte tenu de sa nouvelle situation familiale, se trouve par conséquent fortement réduit. De plus, et sans toutefois les minimiser, trois des huit condamnations prononcées à l'encontre du recourant l'ont uniquement été pour séjour illégal (que ce soit sur le base de l'aLSEE ou de la LEtr), infractions pour lesquelles ce dernier ne peut en principe plus se faire condamner depuis l'obtention de son titre de séjour. Cela conduit à réduire encore plus le caractère actuel de la menace pour l'ordre public que pourrait représenter le recourant. Celui-ci n'a en outre jamais été formellement averti par les autorités de la possibilité d'une révocation de son autorisation de séjour UE/AELE en cas de persévérance dans la délinquance. Finalement, il ne ressort pas de l'arrêt entrepris que le recourant percevrait des prestations de l'aide sociale ou présenterait une situation financière obérée (ni poursuites, ni actes de défaut de biens ne sont évoqués). Dans ces conditions, la mesure ordonnée par le Service cantonal et confirmée par l'autorité précédente ne saurait être considérée comme étant adéquate à la situation de fait, dès lors que le recourant ne représente, à ce jour, pas une menace actuelle et réelle d'une certaine gravité pour l'ordre public.
5.3. Il se justifie donc d'admettre le recours, d'annuler l'arrêt du 18 mars 2016 du Tribunal cantonal et de maintenir l'autorisation de séjour UE/AELE du recourant. Celui-ci doit toutefois être rendu attentif que le maintien de son autorisation de séjour UE/AELE implique qu'il ne commette plus de nouvelles infractions à l'avenir. S'il devait récidiver, il s'exposerait à des mesures d'éloignement (cf. arrêts 2C_370/2012 du 29 octobre 2012 consid. 3.2; 2C_902/2011 du 14 mai 2012 consid. 3). Il y a donc lieu de lui adresser un avertissement formel en ce sens (art. 96 al. 2 LEtr).
6.
Compte tenu de l'issue du recours, notamment de son irrecevabilité quant aux recourantes 2 et 3, il se justifie de mettre une partie des frais à la charge des recourants, solidairement entre eux (art. 66 al. 1, 4 et 5 LTF). Les recourants ont droit à une indemnité de partie réduite (<ref-law>), à charge du canton de Vaud. Le recours, en tant qu'il concerne les recourantes 2 et 3, étant d'emblée dénué de chances de succès, la demande d'assistance judiciaire est rejetée dans la mesure où elle n'est pas sans objet (<ref-law>). La cause est renvoyée au Tribunal cantonal pour qu'il procède à une nouvelle répartition des frais et dépens de la procédure qui s'est déroulée devant lui (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est admis dans la mesure où il est recevable. L'arrêt rendu le 18 mars 2016 par le Tribunal cantonal du canton de Vaud est annulé. L'autorisation de séjour UE/AELE du recourant 1 est maintenue.
2.
Un avertissement est adressé à A.X._, dans le sens des considérants.
3.
La demande d'assistance judiciaire est rejetée dans la mesure où elle n'est pas sans objet.
4.
Des frais judiciaires réduits, arrêtés à 600 fr., sont mis à la charge des recourants, solidairement entre eux.
5.
Une indemnité de partie, arrêtée à 1'300 fr., est allouée aux recourants, à charge du canton de Vaud.
6.
La cause est renvoyée au Tribunal cantonal pour nouvelle décision sur les frais et dépens de la procédure devant lui.
7.
Le présent arrêt est communiqué au représentant des recourants, au Service de la population et au Tribunal cantonal du canton de Vaud, Cour de droit administratif et public, ainsi qu'au Secrétariat d'Etat aux migrations.
Lausanne, le 14 septembre 2016
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président : Seiler
Le Greffier : Tissot-Daguette