Sachverhalt: A. A._ (geb. 1979) ist türkischer Staatsangehöriger kurdischer Ethnie. Er gelangte im Mai 2006 in die Schweiz und stellte ein Asylgesuch. Das Bundesamt für Migration (BFM; ab 1.1.2015: Staatssekretariat für Migration, SEM) wies dieses am 14. Mai 2007 ab und wies ihn aus der Schweiz weg. Zugleich stellte das Bundesamt jedoch fest, dass A._ die Flüchtlingseigenschaft erfülle und der Vollzug der Wegweisung unzulässig sei. Deshalb schob es den Vollzug zugunsten der vorläufigen Aufnahme in der Schweiz auf. B._ (geb. 1991) ist ebenfalls kurdischstämmige, türkische Staatsangehörige. Sie lebt in der Türkei und stellte im Juli 2011 auf der Schweizer Botschaft in Ankara ein Gesuch für einen Aufenthalt von mehr als 90 Tagen zwecks Familiennachzug.Ziel des Gesuchs war es, mit A._in der Schweiz die Ehe einzugehen. Die beiden stellten beim Zivilstandskreis Bern-Mittelland ausserdem ein Gesuch um Vorbereitung der Eheschliessung. B. Das Amt für Migration und Personenstand des Kantons Bern trat auf das Begehren nicht ein. Eine dagegen erhobene Beschwerde bei der Polizei- und Militärdirektion des Kantons Bern blieb erfolglos. Das dagegen erhobene Rechtsmittel wies das Verwaltungsgericht des Kantons Bern am 16. September 2013 ab. C. Gegen das kantonal letztinstanzliche Urteil des Verwaltungsgerichts des Kantons Bern erheben B._ und A._ am 18. Oktober 2013 Beschwerde in öffentlich-rechtlichen Angelegenheiten. Sie beantragen, die Vorinstanz sei anzuweisen, der Beschwerdeführerin die Einreise zwecks Heirat mit dem Beschwerdeführer in der Schweiz zu ermöglichen und ihr eine Kurzaufenthaltsbewilligung für die Vorbereitung der Eheschliessung zu erteilen. Sodann beantragen sie die unentgeltliche Rechtspflege. Das Bundesamt, die Vorinstanz und die Polizei- und Militärdirektion des Kantons Bern beantragen die Abweisung der Beschwerde; das kantonale Migrationsamt hat auf eine Vernehmlassung verzichtet.