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.

Erwägungen:
1. Die Vorinstanz erwägt, dem Beschwerdeführer müsse eine ungünstige Prognose gestellt werden. Diese Auffassung stütze sich insbesondere auf das psychiatrische Gutachten von Dr. med. G._ vom 7. Oktober 2009 (vorinstanzliche Akten, act. 10/89), wonach von einer mittelschweren Rückfallgefahr auszugehen und aus psychiatrisch-psychologischer Sicht eine bedingte Entlassung unverantwortbar sei. Unter den gegebenen Umständen falle eine bedingte Entlassung zurzeit ausser Betracht (vorinstanzliches Urteil, E. 4.3 S. 10).
2. 2.1 Der Beschwerdeführer macht geltend, es sei unzulässig, dass das Amt für Justizvollzug des Kantons Zürich die Absolvierung einer Therapie verlange, obschon das Gericht seinerzeit keine Massnahme angeordnet habe (Beschwerde, S. 5 f. N. 13). Auf dieses Vorbringen zu den Erwägungen des Amts für Justizvollzug ist nicht einzutreten. Dessen Entscheid ist nicht Gegenstand des bundesgerichtlichen Verfahrens. Anfechtungsobjekt bildet einzig der kantonal letztinstanzliche Entscheid der Vorinstanz vom 7. April 2011 (<ref-law>). Darin erwägt diese, eine Therapie und Deliktaufarbeitung werde zwar nicht verlangt, sei indessen eine wichtige Möglichkeit zur Reduzierung der Rückfallgefahr (vorinstanzliches Urteil, E. 4.3 S. 9 f.).
2.2 Der Beschwerdeführer bringt vor, die Vorinstanz verstosse gegen <ref-law>, indem sie zu Unrecht von einer ungünstigen Prognose ausgehe. Zum einen sei zu berücksichtigen, dass er über keine einschlägigen Vorstrafen verfüge und vor der Verbüssung seiner Strafe während zehn Jahren mit einer Freundin und deren Kind zusammen in Spanien gelebt habe, ohne dass es zu Straftaten gekommen sei. Bei den Delikten, die er angeblich begangen haben soll, handle es sich um Beziehungsdelikte. Aussenstehende Personen seien nicht betroffen gewesen. Daher stelle er keine Gefahr für die Öffentlichkeit dar. Alleine aufgrund der Tatsache, dass er nach wie vor bestreite, die ihm vorgeworfenen Straftaten begangen zu haben, dürfe nicht von einer ungünstigen Prognose ausgegangen werden. Eine Pflicht, sich zur Tat zu bekennen, bestehe nicht und Schuldeinsicht sei keine notwendige Voraussetzung für ein künftiges Leben ohne Straftaten (Beschwerde, S. 6 f. N. 14).
Die Vorinstanz unterlasse es zudem, zur Frage Stellung zu nehmen, ob das Rückfallrisiko bei einer bedingten Entlassung höher sei als bei Vollverbüssung der Strafe (sog. Differenzialprognose). Selbst wenn eine Gefahr von ihm ausginge, sei nicht davon auszugehen, das Absitzen bis zum Strafende mindere das Rückfallrisiko. Demzufolge bestehe kein Anlass, ihm die bedingte Entlassung zu verweigern. Das psychiatrische Gutachten begründe seine Empfehlung, die bedingte Entlassung zu verweigern, damit, dass zunächst Vollzugslockerungen wie Urlaube und eine Auseinandersetzung mit dem partnerschaftlichen Beziehungsverhalten zu erfolgen hätten. Indessen werde nicht dargelegt, inwiefern dies zu einer Reduktion der Rückfallgefahr im Zeitraum zwischen bedingter Entlassung und effektivem Strafende führe (Beschwerde, S. 7 ff. N. 15 f.).
Eine bedingte Entlassung sei auch in spezialpräventiver Hinsicht angebracht. Ein Verbleiben im Gefängnis verstärke die Unfähigkeit, ein normkonformes Leben in Freiheit führen zu können. Eine erfolgreiche Wiedereingliederung in die Gesellschaft liege im öffentlichen Interesse (Beschwerde, S. 10 f. N. 17 f.).
3. 3.1 Gemäss <ref-law> ist der Gefangene nach Verbüssung von zwei Dritteln, mindestens aber drei Monaten seiner Strafe, bedingt zu entlassen, wenn es sein Verhalten im Strafvollzug rechtfertigt und nicht anzunehmen ist, er werde weitere Verbrechen oder Vergehen begehen. Die zuständige Behörde hat von Amtes wegen zu prüfen, ob der Gefangene bedingt entlassen werden kann. Dabei hat sie diesen anzuhören und einen Bericht der Anstaltsleitung einzuholen (<ref-law>).
Die bedingte Entlassung stellt die Regel und die Verweigerung die Ausnahme dar. Von diesem Grundsatz darf nur aus guten Gründen abgewichen werden. In dieser letzten Stufe des Strafvollzugs soll der Entlassene den Umgang mit der Freiheit erlernen. Diesem spezialpräventiven Zweck stehen die Schutzbedürfnisse der Allgemeinheit gegenüber, welchen umso höheres Gewicht beizumessen ist, je hochwertiger die gefährdeten Rechtsgüter sind. Die Prognose über das künftige Wohlverhalten ist in einer Gesamtwürdigung zu erstellen, welche nebst dem Vorleben, der Persönlichkeit und dem Verhalten des Täters während des Strafvollzugs vor allem dessen neuere Einstellung zu seinen Taten, seine allfällige Besserung und die nach der Entlassung zu erwartenden Lebensverhältnisse berücksichtigt (<ref-ruling> E. 2.2 f. mit Hinweisen). Im Sinne einer Differenzialprognose sind zudem die Vorzüge und Nachteile der Vollverbüssung der Strafe denjenigen einer Aussetzung eines Strafrestes gegenüberzustellen (<ref-ruling> E. 4a und 5b/bb). Dabei steht der zuständigen Behörde ein Ermessensspielraum zu. Das Bundesgericht greift in die Beurteilung der Bewährungsaussicht nur ein, wenn sie ihr Ermessen über- oder unterschritten oder missbraucht und damit Bundesrecht verletzt hat (<ref-ruling> E. 2.3).
3.2 Der Beschwerdeführer hat am 4. Oktober 2010 zwei Drittel seiner Strafe verbüsst, womit das zeitliche Erfordernis von <ref-law> für eine bedingte Entlassung erfüllt ist. Ebenfalls steht fest, dass sich der Beschwerdeführer im Strafvollzug wohl verhalten hat (vorinstanzliches Urteil, E. 4.2 S. 7 f.). Demzufolge hängt der Entscheid über die bedingte Entlassung einzig davon ab, ob ihm eine günstige Prognose im Sinne von <ref-law> gestellt werden kann.
3.3 Die vorinstanzliche Beurteilung der Legalprognose ist nicht zu beanstanden. Die Vorinstanz nimmt eine Gesamtwürdigung der relevanten Faktoren zur Beurteilung der Prognose über das künftige Wohlverhalten vor und verweist im Übrigen auf die Erwägungen der Direktion der Justiz und des Innern des Kantons Zürich, deren Entscheid sie stützt (vorinstanzliches Urteil, E. 4.3 S. 10). Sie erachtet massgeblich die Täterpersönlichkeit des Beschwerdeführers als prognostisch relevant, insbesondere dessen Einstellung zu seinen Taten. Dies stimmt mit der bundesgerichtlichen Rechtsprechung überein (E. 3.1 hievor). Der Beschwerdeführer bestreitet nach wie vor die Begehung der Straftaten, für die er rechtskräftig verurteilt wurde. Auch wenn die Uneinsichtigkeit eines Straftäters grundsätzlich nicht ohne weiteres gegen dessen bedingte Entlassung spricht, so ist die fehlende Tataufarbeitung dennoch prognoserelevant. Das psychiatrische Gutachten weist denn auch darauf hin, die fehlende Einsicht und Auseinandersetzung mit den Taten sei in legalprognostischer Hinsicht als gravierend ungünstig zu beurteilen (vorinstanzliche Akten, act. 10/89 S. 44 ff.). Das Vorbringen des Beschwerdeführers, wonach ihm nicht alleine aufgrund der fehlenden Einsicht eine ungünstige Prognose gestellt werden dürfe, ist unbegründet. Die Vorinstanz beurteilt dies zwar in Übereinstimmung mit dem psychiatrischen Gutachten als gewichtiges Kriterium, berücksichtigt indessen auch weitere Faktoren. Sie erwägt, der Beschwerdeführer weise keine einschlägigen Vorstrafen auf und habe nach den begangenen Taten mehrere Jahre mit einer Frau und deren Kind zusammengelebt. Indessen ändere dies nichts an der laut psychiatrischem Gutachten gestellten Diagnose einer kompensatorischen Pädophilie mit sexuellem Interesse an minderjährigen Mädchen und der damit einhergehenden mittelschweren Gefahr neuerlicher Straftaten. Insbesondere sei davon auszugehen, dass die Beherrschbarkeit der attestierten Neigungen nach wie vor instabil bzw. nur gegeben sei, wenn er in einer funktionierenden Partnerschaft lebe, in der seine sexuellen Bedürfnisse genügend Befriedigung fänden (vorinstanzliches Urteil, E. 4.3 S. 9). Gegen diese Einschätzung, die in Übereinstimmung mit dem psychiatrischen Gutachten steht, ist nichts einzuwenden (vorinstanzliche Akten, act. 10/89 S. 44).
Entgegen der Ansicht des Beschwerdeführers vertritt die Vorinstanz nicht die Auffassung, er stelle eine Gefahr für x-beliebige Drittpersonen dar. Auch wenn bei Delikten, die in einem Beziehungsgeflecht verübt werden, allgemein davon ausgegangen wird, die Täter unterlägen einem geringeren Rückfallrisiko als solche, die sich an fremden Opfern vergehen (vorinstanzliche Akten, act. 10/89 S. 43), bedeutet dies nicht, dass bei Übergriffen im familiären Rahmen keine Rückfallgefahr vorliegt. Weiter erwägt die Vorinstanz zu Recht, dass ein hochwertiges Rechtsgut (sexuelle Integrität von Kindern) betroffen ist. In solchen Fällen darf ein weniger hohes prognostisches Risiko eingegangen werden als bei der Gefährdung minderer Rechtsgüter (<ref-ruling> E. 2a).
Die Vorinstanz äussert sich nicht zur Frage der Differenzialprognose (E. 3.1 hievor). Das psychiatrische Gutachten weist indessen darauf hin, dass vor einer allfälligen bedingten Entlassung Vollzugslockerungen (begleitete und unbegleitete Urlaube sowie Übertritt in den offenen Vollzug) durchgeführt werden sollen und dem Beschwerdeführer im Rahmen eines therapeutischen Angebots die Möglichkeit zu bieten ist, sich, wenn schon nicht mit seinen Straftaten, so zumindest mit seinem partnerschaftlichen Beziehungsverhalten auseinanderzusetzen (vorinstanzliche Akten, act. 10/89 S. 50). Zum Zeitpunkt des Entscheids über die bedingte Entlassung hatten weder Therapien noch Vollzugslockerungen stattgefunden (vorinstanzliche Akten, act. 4 E. 3.1 f.). Die Fortführung des Strafvollzugs bietet demnach die Möglichkeit, die Rückfallgefahr zu mindern. Unbehelflich ist das Vorbringen des Beschwerdeführers, es werde nicht dargelegt, inwiefern Vollzugslockerungen oder eine Therapie zu einer Reduktion der Rückfallgefahr im Zeitraum zwischen bedingter Entlassung und effektivem Strafende führen sollen.
Der angefochtene Entscheid verletzt kein Bundesrecht. Die Vorinstanz würdigt die relevanten Kriterien zur Beurteilung der Legalprognose zutreffend, ohne den ihr zustehenden Ermessensspielraum zu überschreiten oder zu missbrauchen. Insbesondere ist nicht ersichtlich, aus welchen Gründen von den Erkenntnissen im psychiatrischen Gutachten bzw. der Empfehlung, den Beschwerdeführer nicht bedingt zu entlassen (vorinstanzliche Akten, act. 10/89 S. 50), abzuweichen ist.
4. Der Beschwerdeführer beantragt die unentgeltliche Rechtspflege für die vorangehenden Verfahren. Die Vorinstanz hat dieses Begehren gestützt auf § 16 Abs. 1 des Verwaltungsrechtspflegegesetzes des Kantons Zürich vom 24. Mai 1959 (VRG; LS 175.2) wegen Aussichtslosigkeit der Begehren abgewiesen, was bei diesem Verfahrensausgang nicht zu beanstanden ist. Abgesehen davon könnte der Entscheid in diesem Punkt nur auf Willkür überprüft werden. Eine solche Rüge wurde nicht erhoben.
5. Die Beschwerde ist abzuweisen, soweit darauf einzutreten ist. Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung ist ebenfalls abzuweisen, da die Beschwerde von vornherein aussichtslos war (Art. 64 Abs. 1 und 2 BGG). Bei diesem Ausgang des Verfahrens sind die bundesgerichtlichen Kosten dem Beschwerdeführer aufzuerlegen (<ref-law>). Seiner finanziellen Lage ist bei der Bemessung der Gerichtsgebühr Rechnung zu tragen (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung wird abgewiesen.
3. Die Gerichtskosten von Fr. 800.-- werden dem Beschwerdeführer auferlegt.
4. Dieses Urteil wird den Parteien und dem Verwaltungsgericht des Kantons Zürich, 3. Abteilung, schriftlich mitgeteilt.
Lausanne, 19. Juli 2011
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin:
Mathys Horber