Sachverhalt: A. X._ wurde am 18. März 2004 wegen Vergewaltigung und sexueller Nötigung zu einer Zuchthausstrafe von 4 Jahren verurteilt. Der Vollzug der Strafe wurde zugunsten einer Verwahrung aufgeschoben. B. Im Rahmen der jährlichen Überprüfung lehnte das Amt für Justizvollzug des Kantons Zürich am 26. August 2015 die bedingte Entlassung von X._ ab. Gegen die Verfügung des Amtes für Justizvollzug erhob X._ Rekurs bei der Direktion der Justiz und des Inneren des Kantons Zürich, welche das Rechtsmittel am 24. November 2015 abwies. Die gegen diesen Entscheid erhobene Beschwerde wies das Verwaltungsgericht des Kantons Zürich am 13. September 2016 ab. C. X._ führt Beschwerde in Strafsachen. Er beantragt, das Urteil des Verwaltungsgerichts sei aufzuheben und die Sache zu neuer Entscheidung an dieses zurückzuweisen. Für die Prüfung der bedingten Entlassung im vorinstanzlichen Verfahren sei ein aktuelles und unabhängiges medizinisches Gutachten einzuholen. Eventualiter sei die Entlassung wegen Verletzung des Abstandsgebotes anzuordnen. X._ ersucht um unentgeltliche Rechtspflege und Verbeiständung. Das Amt für Justizvollzug und das Verwaltungsgericht beantragen, die Beschwerde sei abzuweisen. X._ replizierte.