Faits: A. B._, ressortissante de Côte d'Ivoire née en 1983, a déposé le 19 avril 2010 une demande d'autorisation d'entrée en Suisse auprès de l'Ambassade de Suisse à Abidjan en vue d'épouser A._, ressortissant suisse né en 1952. Le 18 juin 2010, elle a également déposé une demande d'exécution de la procédure préparatoire au mariage. Le fiancé a été entendu le 2 septembre 2010 à l'Office de l'état civil de Lausanne. Quant à la fiancée, elle a été auditionnée le 30 septembre 2010 à l'Ambassade de Suisse à Abidjan. B. B.a. Par décision du 3 février 2011, l'Office de l'état civil de Lausanne a refusé de prêter son concours à la célébration du mariage, en raison de l'intention manifeste de la fiancée d'abuser de cette institution dans le but d'éluder les dispositions sur l'admission et le séjour des étrangers. Le recours formé par le fiancé à l'encontre de cette décision a été déclaré irrecevable le 21 mars 2011, faute du paiement de l'avance de frais. Le 8 août 2011, le Service de la population du canton de Vaud (ci-après: SPOP) a refusé de délivrer à la fiancée une autorisation d'entrée en Suisse en vue du mariage. Le 30 septembre 2011, les fiancés ont demandé à la Direction de l'état civil de reconsidérer sa décision du 3 février 2011. Le même jour, ils ont également demandé au SPOP de délivrer une autorisation de séjour en faveur de la fiancée, exposant qu'elle avait dans l'intervalle fui son pays en raison de la guerre civile et de massacres commis dans son quartier, et s'était réfugiée en Suisse. Le 5 octobre 2011, la Direction de l'état civil a indiqué aux intéressés qu'ils devaient présenter une nouvelle demande d'ouverture d'un dossier de mariage, la précédente procédure ayant été close par décision du 3 février 2011, et le recours déposé contre cette dernière ayant été déclaré irrecevable. B.b. A la suite de la demande déposée le 12 octobre 2011, une nouvelle procédure préparatoire de mariage a été ouverte. Les fiancés ont été reçus le 15 décembre 2011 par l'Office de l'état civil pour les formalités du mariage et ont été auditionnés. Estimant se trouver en présence d'un projet de mariage de complaisance au sens de l'art. 97a CC, l'Office de l'état civil a transmis, le 23 décembre 2011, le dossier de mariage à la Direction de l'état civil pour qu'elle se détermine. Le 31 janvier 2012, la Direction de l'état civil a relevé que la fiancée ne disposait d'aucun titre de séjour en Suisse. Elle a imparti aux fiancés un délai de 30 jours pour démontrer la légalité du séjour conformément aux art. 98 al. 4 CC et 66 al. 2 let. e OEC, à défaut de quoi une décision de non-entrée en matière serait rendue. Par courrier du 24 février 2012, le SPOP a informé les fiancés du fait qu'il avait décidé de ne pas octroyer une " tolérance de séjour " à la fiancée. Saisie d'un recours contre cette décision, la Cour de droit administratif et public du Tribunal cantonal du canton de Vaud l'a annulée pour défaut de motivation par arrêt du 25 avril 2012 et a renvoyé le dossier au SPOP pour nouvelle décision. B.c. Le 9 juillet 2012, la Direction de l'état civil a adressé au SPOP une copie du dossier de mariage ainsi que des principales pièces de la précédente procédure de mariage. Elle a relevé divers éléments qui montraient, selon elle, qu'il existait toujours des indices concluants et manifestes d'un mariage de complaisance. Le 30 juillet 2012, le SPOP a informé les fiancés de son intention de refuser l'octroi d'une autorisation de séjour en vue de mariage à la fiancée, et de prononcer son renvoi de Suisse. Tant les fiancés que la Direction de l'état civil se sont déterminés. Celle-ci a notamment fait valoir, par courrier du 21 septembre 2012, que la fiancée ne disposait toujours pas de titre de séjour légal. La Direction de l'état civil a précisé que, au cas où elle en obtiendrait un, elle préavisait d'ores et déjà négativement sur la célébration du mariage, tout en ajoutant que, si l'Office de l'état civil était d'un avis contraire, il pourrait autoriser cette célébration. Le 3 octobre 2012, le SPOP a refusé de délivrer une autorisation de séjour pour le motif, d'une part, qu'un faisceau d'indices ressortant de la procédure de mariage permettait de considérer qu'il s'agissait d'un cas d'abus de droit au mariage et, d'autre part, que l'intéressée était venue en Suisse avec des faux documents, sans être au bénéfice d'un quelconque visa, et qu'elle y avait séjourné illégalement. Le SPOP a également constaté que son départ de Suisse était possible, licite et exigible, et lui a imparti un délai de trois mois pour quitter le territoire. Le 30 octobre 2012, la fiancée a recouru contre cette décision devant la Cour de droit administratif et public, qui a rejeté le recours par arrêt du 9 avril 2013. Un recours en matière de droit public à l'encontre de cet arrêt est actuellement pendant devant la IIème Cour de droit public du Tribunal fédéral; celle-ci a accordé l'effet suspensif au recours par ordonnance du 22 mai 2013 (dossier n° 2C_437/2013). B.d. Par décision du 4 octobre 2012, l'Office de l'état civil a mis fin à la procédure préparatoire du mariage conformément à l'art. 98 al. 4 CC, la fiancée n'ayant pas établi la légalité de son séjour en Suisse, et a subsidiairement refusé son concours à la célébration du mariage en vertu de l'art. 97a CC, l'abus de droit au mariage étant manifeste en l'espèce. Par acte du 6 novembre 2012, les fiancés ont recouru contre cette décision devant la Cour de droit administratif et public. Ils ont conclu à son annulation et au renvoi de la cause à l'autorité inférieure pour nouvelle instruction et nouvelle décision. La Direction de l'état civil, agissant en tant qu'autorité concernée, s'est déterminée le 10 décembre 2012; agissant en son nom et au nom de l'Office de l'Etat civil, elle a conclu au rejet du recours. Par arrêt du 9 avril 2013, la Cour de droit administratif et public a rejeté le recours et confirmé la décision de l'Office de l'état civil du 4 octobre 2012. C. Par acte du 10 mai 2013, les fiancés interjettent un " recours en matière de droit public " au Tribunal fédéral. Ils concluent à l'annulation de l'arrêt rendu par la Cour de droit administratif et public le 9 avril 2013, et au renvoi de la cause à cette autorité pour complément d'instruction et nouvelle instruction dans le sens des considérants. Des réponses n'ont pas été requises.