Faits: A. X._, ressortissant français né en 1984, a annoncé son arrivée dans le canton de Vaud le 18 octobre 2011. Il a pris domicile à A._, auprès de Y._, ressortissante suisse qu'il avait épousée en 2011 et avec laquelle il avait eu une fille, Z._, née en 2011. Il ressort du casier judiciaire français que l'intéressé a été condamné pénalement à plusieurs reprises soit: - le 29 janvier 2004, par le Tribunal correctionnel de Créteil, à une peine de quatre mois d'emprisonnement avec sursis pour abus de confiance et recel de vol; - le 10 janvier 2006, par le même tribunal, à mille euros d'amende pour recel de bien provenant d'un vol; - le 25 octobre 2007, par le Tribunal correctionnel de Paris, à une peine d'emprisonnement d'un an pour vol en réunion en récidive légale; - le 16 octobre 2008, par le Tribunal correctionnel de Marseille, à une peine d'emprisonnement de cinq ans pour infraction à la législation sur les stupéfiants en récidive légale, association de malfaiteurs, importation et détention de marchandise importée en contrebande. X._, incarcéré depuis le 23 juin 2006, a été mis au bénéfice de la libération conditionnelle le 27 juin 2011, selon jugement du juge de l'application des peines du Tribunal de grande instance d'Evreux. Le 18 octobre 2011, le prénommé a sollicité l'octroi d'une autorisation de séjour dans le canton de Vaud pour y vivre auprès de son épouse. B. Après lui avoir donné l'occasion de s'exprimer, le Service de la population du canton de Vaud (ci-après: le SPOP), par décision du 30 avril 2012, a refusé de délivrer l'autorisation de séjour requise par l'intéressé et a prononcé son renvoi de Suisse. Il s'est fondé sur les condamnations pénales prononcées à son encontre en France et a considéré que l'intérêt public à son éloignement l'emportait sur son intérêt privé à vivre en Suisse. X._ a recouru contre cette décision auprès de la Cour de droit administratif et public du Tribunal cantonal du canton de Vaud (ci-après: le Tribunal cantonal), laquelle l'a débouté par arrêt du 18 février 2013. C. X._ forme un recours en matière de droit public auprès du Tribunal fédéral. Outre l'effet suspensif et le bénéfice de l'assistance judiciaire, il requiert, sous suite de frais et dépens, l'annulation de l'arrêt du 18 février 2013 et de la décision du SPOP du 30 avril 2012, ainsi que l'octroi d'une autorisation de séjour. Subsidiairement, il demande le renvoi de la cause à l'autorité précédente pour nouvelle décision dans le sens des considérants. L'Office fédéral des migrations conclut au rejet du recours, alors que le SPOP et le Tribunal cantonal renoncent à se déterminer. Par ordonnance du 25 mars 2013, le Président de la IIème Cour de droit public a accordé l'effet suspensif au recours.