Sachverhalt: A. Das Obergericht des Kantons Zürich verurteilte X._ am 25. November 1999 wegen mehrfacher sexueller Nötigung, Vergewaltigung und mehrfacher sexueller Handlungen mit Kindern zum Nachteil seiner Stieftochter unter Anrechnung der erstandenen Untersuchungshaft von 70 Tagen zu fünfeinhalb Jahren Zuchthaus. Seit dem 19. Mai 2008 befindet er sich in der Strafanstalt Pöschwies, nachdem er am 16. April 2007 in Spanien verhaftet und an die Schweiz ausgeliefert worden war. Zwei Drittel der Strafe waren am 4. Oktober 2010 verbüsst. Reguläres Strafende ist der 4. August 2012. B. X._ ersuchte am 17. Mai 2010 um die bedingte Entlassung aus dem Strafvollzug auf den 4. Oktober 2010. Mit Verfügung vom 16. September 2010 wies der Sonderdienst der Bewährungs- und Vollzugsdienste des Amtes für Justizvollzug des Kantons Zürich das Gesuch ab. X._ ersuchte zudem die Direktion der Strafanstalt Pöschwies darum, ihm per 1. August 2011 einen Führungsbericht zuzustellen und darin zur bedingten Entlassung Stellung zu nehmen. Den gegen die Gesuchsabweisung von X._ erhobenen Rekurs wies die Direktion der Justiz und des Innern des Kantons Zürich am 29. November 2010 ab. Das Verwaltungsgericht des Kantons Zürich wies seine Beschwerde mit Urteil vom 7. April 2011 ebenfalls ab. C. X._ erhebt Beschwerde in Strafsachen. Er beantragt, das Urteil des Verwaltungsgerichts vom 7. April 2011 sei aufzuheben, und er sei bedingt aus dem Strafvollzug zu entlassen. Eventualiter sei die Sache zu neuer Entscheidung bzw. Vornahme weiterer Abklärungen an das Verwaltungsgericht zurückzuweisen. Es sei ihm für das vorinstanzliche Verfahren eine Entschädigung in der Höhe von Fr. 2'500.-- zuzüglich 8% MWST zuzusprechen. Zudem ersucht er um Gewährung der unentgeltlichen Rechtspflege und Verbeiständung für die kantonalen sowie das bundesgerichtliche Verfahren.