Faits: A. A.a. X._, ressortissant kosovar né en 1974, est entré illégalement en Suisse en septembre 2008. Il a été interpellé par la police fribourgeoise le 30 août 2009; à cette occasion, il a indiqué qu'il vivait et travaillait en Suisse depuis le 1er octobre 2008. Le 28 octobre 2009, le Service de la population et des migrants du canton de Fribourg a rendu une décision de renvoi de Suisse à l'encontre de l'intéressé. X._ a fait l'objet d'une mesure d'interdiction d'entrée en Suisse prononcée par l'Office fédéral des migrations le 29 octobre 2009. Par ordonnance pénale du 9 décembre 2009, le juge d'instruction cantonal fribourgeois a condamné l'intéressé pour séjour et travail illégaux. A.b. Le 22 janvier 2010, X._ et A._, ressortissante mauricienne née en 1946, titulaire d'une autorisation d'établissement en Suisse, ont formé auprès de l'Office de l'état civil de Lausanne une demande d'ouverture d'un dossier de mariage. Les fiancés ont été entendus séparément le 10 juin 2010 par l'Officier de l'état civil de Lausanne. Celui-ci a transmis le dossier des intéressés à la Direction de l'état civil du canton de Vaud le 21 juin 2010 en lui indiquant présumer l'existence d'un mariage de complaisance. Parallèlement, le 5 février 2010, X._ a sollicité auprès du bureau des étrangers de la commune de Prilly l'octroi d'une autorisation de séjour en vue de son mariage avec A._. Par décision du 27 septembre 2010, l'Office de l'état civil a refusé son concours à la célébration du mariage de X._ et A._. La Cour de droit administratif et public du Tribunal cantonal du canton de Vaud (ci-après: le Tribunal cantonal) a rejeté le recours déposé par les intéressés et confirmé la décision querellée le 22 février 2011. Le Tribunal fédéral a rejeté dans la mesure de sa recevabilité le recours contre cet arrêt le 9 août 2011 (cause 5A_225/2011). Le 7 décembre 2010, à la suite de la dénonciation de la commune de Prilly, le Juge d'instruction de l'arrondissement de Lausanne a condamné X._ pour infraction à la législation sur les étrangers. Par décision du 24 octobre 2011, le Service de la population du canton de Vaud (ci-après: le Service de la population) a refusé à X._ l'octroi d'une autorisation de séjour. X._ a quitté le territoire suisse le 7 octobre 2011. Le 24 octobre 2011, X._ et A._ se sont mariés au Kosovo. A la suite du mariage, X._ a sollicité la reconsidération de la décision du Service de la population du 24 octobre 2011. A.c. Le 30 novembre 2011, X._ a déposé, depuis le Kosovo, une demande d'entrée, respectivement de séjour, en vue de rejoindre son épouse en Suisse. Par courrier du 1er décembre 2011, l'Ambassadeur de Suisse au Kosovo a indiqué au Service de la population que A._ ne parlait pas l'albanais, que X._ avait des connaissances très limitées en français et qu'il avait l'intention de demander le regroupement familial pour ses deux fils B._, né en 1999, et C._, né en 2004, issus d'une union avec une compatriote. Le 19 avril 2012, X._ a été entendu à l'Ambassade de Suisse à Pristina (Kosovo). Lors de cette audition, il a notamment indiqué qu'il n'avait pas épousé A._ dans le seul but d'obtenir un titre de séjour en Suisse. Le 5 juin 2012, le Service de la population a informé X._ de son intention de refuser l'octroi d'une autorisation d'entrée en Suisse. Par décision du 21 novembre 2012, après avoir entendu l'intéressé, le Service de la population a refusé de lui octroyer une autorisation d'entrée, respectivement de séjour. Saisi d'un recours contre cette décision, le Tribunal cantonal l'a rejeté par arrêt du 15 mai 2013. Il a considéré en substance qu'un faisceau d'indices montrait que X._ ne souhaitait manifestement pas fonder une communauté conjugale avec A._, mais qu'il entendait éluder les dispositions sur l'admission et le séjour des étrangers en invoquant son mariage avec une personne retraitée nettement plus âgée que lui et au bénéfice d'une autorisation d'établissement. B. Agissant par la voie du recours en matière de droit public, X._ demande au Tribunal fédéral, sous suite de frais et dépens, d'annuler l'arrêt entrepris et de renvoyer la cause à l'autorité intimée pour nouvelle décision. Le Service de la population a renoncé à se déterminer sur le recours et le Tribunal cantonal s'est référé aux considérants de son arrêt. Le recourant a renoncé à formuler des observations complémentaires.