Sachverhalt: A. A._, geboren 1978, und B._, geboren 1981, sind syrisch-kurdischer Herkunft. Sie reisten am 23. Oktober 2002 in die Schweiz; ein Asylgesuch wurde am 10. Januar 2005 zunächst abgewiesen. In Wiedererwägung dieser Verfügung wurde ihnen jedoch am 4. November 2005 aufgrund der Mitgliedschaft von A._ bei der PKK, verbunden mit exilpolitischer Tätigkeit, die Flüchtlingseigenschaft zuerkannt, Asyl indes weiterhin verweigert, weil die aktive Mitgliedschaft in einer bewaffneten Organisation Asylunwürdigkeit zur Folge habe. A._ und B._ wurden dementsprechend als Flüchtlinge vorläufig aufgenommen. Aufgrund der Zugehörigkeit zur Gruppe der Maktumin wurden A._ und B._ sowie ihre Kinder am 30. Mai 2013 als Staatenlose anerkannt, worauf ihnen das Amt für Migration und Zivilrecht des Kantons Graubünden die Aufenthaltsbewilligung erteilte. B. A._ und B._ ersuchten am 17. Juni 2013 um Erteilung der Niederlassungsbewilligung für alle Familienmitglieder. Darauf hätten sie Anspruch, weil sie sich als staatenlos anerkannte Personen seit mehr als fünf Jahren in der Schweiz aufhielten. Das Amt für Migration und Zivilrecht des Kantons Graubünden lehnte dies jedoch am 9. Dezember 2013 ab mit der Begründung, dass die Frist von fünf Jahren erst ab der Anerkennung der Staatenlosigkeit zu laufen beginne. Beschwerden gegen diese Verfügung wurden am 7. April 2014 vom Departement für Justiz, Sicherheit und Gesundheit sowie am 6. Oktober 2015 vom Verwaltungsgericht des Kantons Graubünden abgewiesen. C. A._, B._ sowie ihre drei Kinder A.B.C._, A.B.D._ und A.B.E._ haben am 8. Januar 2016 Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht erhoben. Sie beantragen, den Entscheid des Verwaltungsgerichts des Kantons Graubünden vom 6. Oktober 2015 aufzuheben und ihnen die Niederlassungsbewilligung zu erteilen. Für das bundesgerichtliche Verfahren ersuchen sie um Gewährung der unentgeltlichen Rechtspflege. Das Departement für Justiz, Sicherheit und Gesundheit und das Verwaltungsgericht des Kantons Graubünden wie auch das Staatssekretariat für Migration SEM beantragen Abweisung der Beschwerde, jeweils ohne sich ausführlich vernehmen zu lassen. In einer Stellungnahme vom 18. April 2016 beantragen die Beschwerdeführer, das Staatssekretariat für Migration zu verhalten, inhaltlich zur von ihnen dokumentierten abweichenden Praxis in anderen Kantonen und des Staatssekretariats selbst Stellung zu nehmen.