Sachverhalt: A. A.X._ (geb. 1964) stammt aus Sri Lanka. Er reiste im Jahr 1984 in die Schweiz ein. 1987 heiratete er die Schweizer Bürgerin Z._. Aus dieser Ehe gingen die Kinder V.Z._ (geb. 1988) und W.Z._ (geb. 1991) hervor. Die Ehe wurde im Jahr 1994 geschieden. Am 15. Oktober 2000 heiratete A.X._ in Sri Lanka die Schweizer Bürgerin B.X._ (geb. 1972). Aus dieser Verbindung sind die drei Kinder hervorgegangen: C.X._ (geb. 1992), D.X._ (geb. 2005) und E.X._ (geb. 2010). A.X._ war im Besitz der Aufenthaltsbewilligung, welche ihm letztmals bis zum 1. März 2009 verlängert wurde. Während seines Aufenthalts ist A.X._ wie folgt straffällig worden: Mit Strafmandat vom 19. Februar 1993 verurteilte ihn das Kreisamt Chur wegen grober Verletzung der Verkehrsregeln zu einer Busse in der Höhe von Fr. 500.--. Mit Urteil vom 17. März 1994 verurteilte ihn das Kreisgericht Chur wegen mehrfacher Veruntreuung zu drei Monaten Gefängnis bedingt. Daraufhin verwarnte die Fremdenpolizei des Kantons Graubünden A.X._ und teilte ihm mit Verfügung vom 11. Mai 1994 mit, dass seine Aufenthaltsbewilligung bei einer allfälligen weiteren strafrechtlichen Verurteilung erlöschen würde. Nach der ausländerrechtlichen Verwarnung wurde A.X._ wie folgt straffällig: Am 16. Mai 2007 verurteilte ihn das Kreispräsidium Chur wegen Unterlassens der Buchführung sowie wegen Vergehens gegen das Bundesgesetz über die Alters- und Hinterlassenenversicherung (Bundesgesetz vom 20. Dezember 1946 über die Alters- und Hinterlassenenversicherung vom 20. Dezember 1946; AHVG [SR 831.10]) zu einer Geldstrafe von 30 Tagessätzen bei einer Probezeit von zwei Jahren sowie einer Busse von Fr 1'000.--. Am 26. Februar 2008 verurteilte ihn das Kreispräsidium Chur wegen Vergehen gegen das AHVG sowie Unterlassens der Buchführung zu einer Geldstrafe zu 20 Tagessätzen bei einer Probezeit von zwei Jahren sowie einer Busse von Fr. 800.--. Am 21. Januar 2010 verurteilte ihn das Bezirksgericht Plessur wegen Tätlichkeit, Drohung, mehrfacher sexueller Handlungen mit Kindern, mehrfachen Versuchs der sexuellen Handlungen mit Kindern, mehrfacher Pornografie, Pornografie gemäss Art. 197 Ziff. 3bis StGB, mehrfachen Inzests zum Nachteil der Tochter C.X._ und wegen mehrfachen Versuchs des Inzests zu einer Freiheitsstrafe von drei Jahren und für die Tätlichkeiten zu einer Busse von Fr. 200.--. Am 4. Februar 2011 verurteilte ihn die Staatsanwaltschaft Graubünden erneut wegen Unterlassens der Buchführung und Widerhandlung gegen das AHVG. Die bedingt ausgesprochenen Geldstrafen vom 16. Mai 2007 und 26. Februar 2008 wurden widerrufen und für vollziehbar erklärt. A.X._ befand sich vom 24. Januar 2011 bis zum 22. Februar 2012 im Strafvollzug. B. Mit Verfügung vom 12. September 2011 verweigerte das Amt für Polizeiwesen und Zivilrecht des Kantons Graubünden die Verlängerung der Jahresaufenthaltsbewilligung von A.X._ und ordnete an, er habe die Schweiz nach Beendigung des Strafvollzugs zu verlassen. Eine gegen diese Verfügung erhobene Eingabe von A.X._ und B.X._ beim Departement für Justiz, Sicherheit und Gesundheit Graubünden blieb erfolglos. Die hiergegen gerichtete Beschwerde an das Verwaltungsgericht des Kantons Graubünden wies dieses mit Urteil vom 19. Juni 2012 ab. C. Mit Eingabe vom 13. September 2012 beantragen A.X._ und B.X._ (Beschwerdeführende bzw. Beschwerdeführer 1 und Beschwerdeführerin 2) dem Bundesgericht, das Urteil vom 19. Juni 2012 sei aufzuheben; die Aufenthaltsbewilligung von A.X._ sei zu verlängern. Zudem ersuchen sie um Gewährung der unentgeltlichen Rechtspflege für die vorinstanzlichen und für das vorliegende Verfahren. Das Verwaltungsgericht des Kantons Graubünden hat innert Frist keine Vernehmlassung eingereicht. Das Bundesamt für Migration beantragt, die Beschwerde sei abzuweisen. Das Departement für Justiz, Sicherheit und Gesundheit Graubünden hat sich nicht vernehmen lassen. Mit Verfügung vom 19. September 2012 hat das präsidierende Mitglied der Beschwerde aufschiebende Wirkung zuerkannt.