Sachverhalt: A. Der irakische Staatsbürger A.A._ (geb. 1976) reiste am 7. Dezember 1998 in die Schweiz ein und ersuchte erfolglos um Asyl. Nach einer längeren Sistierung der Ausreisefristen für abgewiesene irakische Asylbewerber ordnete das Bundesamt für Migration am 11. November 2005 wiedererwägungsweise seine vorläufige Aufnahme an. Am 21. Juli 2006 heiratete er die Schweizer Bürgerin B._ (geb. 1977), worauf ihm eine Aufenthaltsbewilligung erteilt wurde. Die Ehe blieb kinderlos. Am 3. November 2011 verurteilte das Obergericht des Kantons Zug A.A._ in zweiter Instanz wegen versuchter vorsätzlicher Tötung, begangen am 22. Januar 2010, zu einer Freiheitsstrafe von sieben Jahren. Seit seiner Festnahme am 25. Januar 2010 befindet sich A.A._ in Haft bzw. im Strafvollzug. B. Am 27. August 2012 verfügte das Amt für Migration des Kantons Zug die Nichtverlängerung seiner Aufenthaltsbewilligung und wies A.A._ aus der Schweiz und dem Schengenraum weg. Eine Beschwerde beim Regierungsrat des Kantons Zug blieb erfolglos. Die dagegen erhobene Beschwerde wies das Verwaltungsgericht des Kantons Zug mit Urteil vom 26. November 2013 ab. C. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 17. Januar 2014 beantragen A.A._ und B.A._ die Aufhebung des angefochtenen Urteils. Es sei A.A._ die Aufenthaltsbewilligung zu belassen. Zudem ersuchen sie um unentgeltliche Rechtspflege und Verbeiständung. Während der Regierungsrat des Kantons Zug auf eine Vernehmlassung verzichtet, beantragen das Verwaltungsgericht des Kantons Zug und das Bundesamt für Migration die Abweisung der Beschwerde. Dem Gesuch um aufschiebende Wirkung wurde mit Präsidialverfügung vom 23. Januar 2014 entsprochen.