Faits: A. X._, ressortissant du Bénin né en 1977, est entré le 1er octobre 2001 en Suisse, où il a déposé une demande d'asile, sous un faux nom (soit Z._) et une fausse date de naissance (soit 1984). Cette demande a été rejetée par décision de l'Office fédéral des réfugiés du 22 février 2002. Le recours interjeté à son encontre a été déclaré irrecevable le 1er mai 2002 par la Commission suisse de recours en matière d'asile. L'intéressé a disparu dans la clandestinité le 16 avril 2002. X._ a eu deux enfants au Bénin: A._, né en 2003, et B._, né en 2006. Le 20 novembre 2007, X._ est revenu sans visa en Suisse, où il a résidé illégalement dans le Canton de Vaud dès le 10 janvier 2008. Du 30 octobre 2008 au 21 avril 2009, il a été détenu en prison préventive à l'établissement de détention de La Chaux-de-Fonds. Il ressort du dossier de X._ les condamnations suivantes, les deux premières ayant été prononcées sous le faux nom de Z._: - le 25 juin 2003: par défaut, peine de six mois de détention pour vol, dommages à la propriété et infraction à la loi fédérale sur les stupéfiants, prononcée par l'Autorité tutélaire du district de La Chaux-de-Fonds; - le 20 avril 2009: peine privative de liberté de quinze mois avec sursis pendant trois ans pour infractions graves à la loi fédérale sur les stupéfiants et à la loi fédérale sur les étrangers, peine partiellement complémentaire à celle de six mois de détention du 25 juin 2003, prononcée par le Tribunal cantonal du Canton de Neuchâtel; - le 9 mars 2011: peine de 120 jours-amende, avec sursis pendant deux ans, le montant du jour-amende étant fixé à 10 fr., pour entrée et séjour illégaux, prononcée par ordonnance pénale du Ministère public de l'arrondissement de Lausanne; - le 4 août 2011: peine pécuniaire de 20 jours-amende avec sursis pendant trois ans, le montant du jour-amende étant fixé à 30 fr., pour faux dans les certificats, peine complémentaire à celle du 9 mars 2011, prononcée par le Ministère public du Canton de Genève. Le 12 novembre 2010, X._ a déposé une demande d'autorisation de séjour en vue d'épouser Y._, ressortissante ivoirienne née en 1977 au bénéfice d'un permis d'établissement. Dans le rapport d'arrivée qu'il a signé le 12 octobre 2010, l'intéressé a indiqué n'avoir effectué aucun séjour en Suisse précédemment et n'avoir fait l'objet d'aucune condamnation. Le 31 décembre 2010, une altercation entre X._ et Y._ a fait l'objet d'un rapport de police et tous deux ont été dénoncés pour troubles à l'ordre et à la tranquillité publics. B. Par décision du 22 mars 2011 notifiée à X._ et Y._, l'Office de l'état civil de Lausanne a déclaré irrecevable leur demande d'ouverture d'une procédure préparatoire de mariage et classé le dossier sans suite, dès lors que X._ ne pouvait se prévaloir d'un séjour légal en Suisse. Le 9 juillet 2011, l'intéressé est retourné au Bénin. Le 15 juillet 2011, X._ et Y._ se sont mariés à Porto-Novo, au Bénin. C. Le 15 novembre 2011, X._ a déposé une demande d'autorisation d'entrée et de séjour par regroupement familial afin de rejoindre son épouse en Suisse. Sur réquisition du Service de la population du canton de Vaud, l'intéressé a été entendu le 2 mars 2012 par l'Ambassade de Suisse au Ghana. Il a en particulier déclaré à cette occasion que son épouse et lui-même s'étaient rencontrés dans une discothèque à Lausanne en 2010, qu'ils avaient vécu ensemble et qu'ils s'aimaient; son épouse était même tombée enceinte en juin 2010, mais avait malheureusement fait une fausse couche. Il a également indiqué que, depuis qu'il était au Bénin, son épouse et lui-même se téléphonaient au moins deux fois par jour, qu'elle était aide-infirmière dans une maison pour personnes âgées, qu'après leur mariage en juillet 2011, elle était revenue fin 2011 au Bénin pour le dépôt de sa demande de visa et y était restée trois semaines et qu'elle avait une tante, une petite soeur et sa fille en Suisse, le reste de sa famille vivant en Côte d'Ivoire. Il a enfin précisé que le mariage avait été décidé par tous deux et qu'il avait différents documents démontrant la réalité du mariage, soit l'acte et le livret de mariage ainsi que les photos et la vidéo du mariage. Sur réquisition du Service de la population du canton de Vaud, Y._ a été entendue le 24 février 2012 par la Police de l'Ouest lausannois. Elle a notamment déclaré avoir rencontré son mari au printemps 2009 dans une discothèque à Lausanne, que la relation qu'elle entretenait avec lui était harmonieuse jusqu'à son départ en juillet 2011 au Bénin et qu'ils s'étaient mariés, à sa demande à elle, parce qu'ils s'aimaient. Elle a également relevé qu'elle était tombée enceinte trois fois, mais que les deux premières fois, elle avait avorté et que la troisième fois avait abouti à une fausse couche. Elle a précisé que son mari l'avait mise au courant de son passé pénal en Suisse avant leur mariage et vouloir demeurer à ses côtés. Après leur avoir donné l'occasion d'exercer leur droit d'être entendu, le Service de la population a refusé, par décision du 10 octobre 2012, l'octroi d'une autorisation d'entrée en Suisse, respectivement de séjour à X._. Le Tribunal cantonal du canton de Vaud a rejeté le 24 janvier 2013 le recours formé par les conjoints contre la décision du Service de la population du canton de Vaud du 10 octobre 2012. D. X._ et Y._ forment un recours en matière de droit public auprès du Tribunal fédéral. Outre la dispense d'avance de frais, ils requièrent en substance, sous suite de frais et dépens, l'octroi d'une autorisation d'entrée et de séjour, subsidiairement le renvoi à l'autorité précédente pour qu'elle agisse en ce sens. Le Service de la population du canton de Vaud et le Tribunal cantonal renoncent à se déterminer sur le recours alors que l'Office fédéral des migrations conclut à son rejet. Le 28 février 2013, le Président de la IIe Cour de droit public a rejeté la requête de dispense d'avance de frais. Par ordonnance du 13 mars 2013, il a autorisé le paiement fractionné de dite avance.