Sachverhalt: A. Der libanesische Staatsbürger X._ (geb. 1972) heiratete am 2. September 2002 die Schweizer Staatsangehörige Z._ (geb. 1966). Er erhielt zunächst eine Aufenthaltsbewilligung und im Herbst 2007 die Niederlassungsbewilligung für den Kanton Zürich. Ein Gesuch um erleichterte Einbürgerung ist hängig. Die erste Ehe von X._ mit W._ wurde am 31. März 2001 resp. 19. Februar 2002 im Libanon geschieden. Die aus dieser Ehe hervorgegangene Tochter Y._ (geb. 25. Dezember 1996) reiste am 8. Oktober 2006 mit einem bis zum 21. November 2006 gültigen Besuchervisum in die Schweiz ein. X._ stellte am 27. Oktober 2006 für seine Tochter ein Gesuch um Aufenthaltsbewilligung im Familiennachzug, obwohl er zuvor zugesichert hatte, für die fristgerechte Wiederausreise seiner Tochter zu sorgen. Die Sicherheitsdirektion des Kantons Zürich wies das Gesuch mit Verfügung vom 12. Juni 2007 ab und setzte Y._ eine Ausreisefrist bis zum 31. Juli 2007. Dagegen liessen Y._ und X._ mit Eingabe vom 12. Juli 2007 Rekurs an den Regierungsrat des Kantons Zürich erheben. Mit Beschluss vom 8. Juli 2009 wies der Regierungsrat den Rekurs betreffend Aufenthaltsbewilligung für Y._ ab. Eine hiergegen am 21. September 2009 erhobene Beschwerde wies das Verwaltungsgericht des Kantons Zürich, 4. Kammer, mit Urteil vom 30. Dezember 2009 ab. B. Mit Eingabe vom 8. Februar 2010 erheben Y._ und X._ Beschwerde in öffentlich-rechtlichen Angelegenheiten beim Bundesgericht. Sie beantragen, der Entscheid des Verwaltungsgerichts vom 30. Dezember 2009 sei aufzuheben und die Sicherheitsdirektion sei anzuweisen, Y._ eine Niederlassungsbewilligung, eventualiter eine Aufenthaltsbewilligung, auszustellen. Subeventualiter wird beantragt, die Sache sei an die Vorinstanz oder an die Sicherheitsdirektion zurückzuweisen. Gerügt wird die Verletzung von Bundes- und Völkerrecht. C. Das Verwaltungsgericht des Kantons Zürich verzichtet auf eine Vernehmlassung. Das Bundesamt für Migration schliesst auf Abweisung der Beschwerde, währenddem sich der Regierungsrat und die Sicherheitsdirektion des Kantons Zürich nicht geäussert haben. D. Mit Verfügung vom 12. Februar 2010 hat der Präsident der II. öffentlich-rechtlichen Abteilung des Bundesgerichts der Beschwerde antragsgemäss die aufschiebende Wirkung zuerkannt.