Sachverhalt: A. A._ (geb. 1978) stammt aus dem Kosovo. Er reiste am 27. November 2005 in die Schweiz ein und heiratete am 21. Dezember 2005 eine in der Schweiz niedergelassene Staatsangehörige der Dominikanischen Republik (geb. 1981). Gestützt auf diese Heirat erhielt er eine Aufenthaltsbewilligung, die letztmals bis 20. Dezember 2009 verlängert wurde. Am 29. Dezember 2011 brachte A._s Ehegattin eine Tochter zur Welt. Der Tochter wurde die Niederlassungsbewilligung erteilt. B. Mit Verfügung vom 28. Mai 2010 wies die Sicherheitsdirektion (Migrationsamt) des Kantons Zürich das Gesuch von A._ um Verlängerung der Aufenthaltsbewilligung ab und setzte ihm Frist zur Ausreise bis 31. Juli 2010. Sie ging von einer Scheinehe aus. Den gegen diese Verfügung erhobenen Rekurs wies der Regierungsrat des Kantons Zürich am 14. November 2012 ab. Das Verwaltungsgericht des Kantons Zürich bestätigte diesen Entscheid mit Urteil vom 15. Mai 2013. C. A._ beantragt vor Bundesgericht, es sei das Urteil des Verwaltungsgerichts des Kantons Zürich vom 15. Mai 2013 unter Erteilung der aufschiebenden Wirkung aufzuheben, sein Gesuch um Verlängerung der Aufenthaltsbewilligung sei gutzuheissen und er sei nicht wegzuweisen. Eventualiter sei die Beschwerdegegnerin anzuweisen, die Aufenthaltsbewilligung des Beschwerdeführers zu verlängern; subeventualiter sei die Sache zur Neubeurteilung an die Vorinstanz zurückzuweisen. Für das bundesgerichtliche Verfahren sei ihm die unentgeltliche Rechtspflege und Verbeiständung zu gewähren. Das Verwaltungsgericht des Kantons Zürich hat darauf verzichtet, eine Vernehmlassung einzureichen. Das Bundesamt für Migration (BFM) und der Regierungsrat des Kantons Zürich beantragen die Abweisung der Beschwerde. Mit Präsidialverfügung vom 28. Juni 2013 erteilte der Abteilungspräsident der Beschwerde die aufschiebende Wirkung. Von der Einforderung des Kostenvorschusses wurde einstweilen abgesehen und ein Entscheid über das Gesuch um unentgeltliche Rechtspflege und Verbeiständung vorbehalten.