Sachverhalt: A. A.X._ (geb. 1976) ist Staatsangehöriger von Bangladesch und reiste am 23. April 2002 als Asylbewerber erstmals in die Schweiz ein. Am 3. September 2002 heiratete er die Schweizer Bürgerin B.X._ (geb. 1982), welche Mutter des aus einer früheren Beziehung hervorgegangen Sohnes C.X._ (geb. 2001) ist. Aufgrund der Heirat erhielt A.X._ eine Aufenthaltsbewilligung für den Kanton Zürich. Am 12. November 2002 brachte B.X._ ihre Tochter D.X._ - ebenfalls aus einer früheren Beziehung hervorgegangen - zur Welt. Am 3. Oktober 2003 wurde das Asylverfahren als durch Rückzug erledigt abgeschrieben. Am 12. Oktober 2005 ging aus der Beziehung von B.X._ mit E._ die Tochter F.X._ hervor. Am 5. Januar 2006 teilte die Sicherheitsdirektion des Kantons Zürich A.X._ mit, sie beabsichtige, ihm den weiteren Aufenthalt im Kanton Zürich zu verweigern, weil er sich rechtsmissbräuchlich auf seine Ehe berufe. Zuvor hatten polizeiliche Ermittlungen den Verdacht einer Scheinehe ergeben. Nachdem sich A.X._ erneut an der Wohnadresse seiner Ehefrau angemeldet hatte und diese schriftlich bestätigte, sie sei zur Wiederaufnahme der Ehegemeinschaft bereit, verlängerte die Sicherheitsdirektion die Aufenthaltsbewilligung und erteilte am 13. November 2007 die Niederlassungsbewilligung für den Kanton Zürich. Mit Verfügung vom 3. Juni 2008 stellte das Bezirksgericht Winterthur fest, dass die Eheleute X._ seit dem 14. Mai 2008 getrennt lebten. B. Nachdem B.X._ erneut bestätigt hatte, eine Scheinehe eingegangen zu sein, widerrief die Sicherheitsdirektion mit Verfügung vom 21. Januar 2009 die Niederlassungsbewilligung von A.X._ und setzte ihm Frist zum Verlassen der Schweiz bis zum 31. März 2009. Dagegen gelangte A.X._ mit Rekurs an den Regierungsrat des Kantons Zürich, der das Rechtsmittel am 15. Juni 2011 abwies. Das hiegegen angerufene Verwaltungsgericht des Kantons Zürich erkannte mit Urteil vom 26. Oktober 2011 auf Abweisung der Beschwerde und setzte die Ausreisefrist neu auf den 31. Dezember 2011 fest. C. Mit Eingabe vom 1. Dezember 2011 erhebt A.X._ Beschwerde in öffentlich-rechtlichen Angelegenheiten. Er beantragt, die Verfügung der Sicherheitsdirektion vom 15. Juni 2011 (recte: 21. Januar 2009) bzw. das Urteil des Verwaltungsgerichts vom 26. Oktober 2011 seien aufzuheben und von einem Widerruf seiner Niederlassungsbewilligung sei abzusehen. Das Verwaltungsgericht des Kantons Zürich verzichtet auf eine Vernehmlassung, während der Regierungsrat des Kantons Zürich sowie das Bundesamt für Migration die Abweisung der Beschwerde beantragen. Mit Verfügung vom 6. Dezember 2011 hat der Präsident der II. öffentlich-rechtlichen Abteilung des Bundesgerichts der Beschwerde antragsgemäss die aufschiebende Wirkung zuerkannt.