Sachverhalt: Sachverhalt: A. Der aus Nigeria stammende, 1965 geborene X._ reiste am 17. Januar 1993 illegal in die Schweiz ein und ersuchte unter dem Namen Z._, angeblich aus Liberia stammend, um Asyl. Mit Verfügung vom 20. September 1993 wies das Bundesamt für Flüchtlinge das Asylgesuch ab. Mit Urteil vom 26. November 1993 wies die Schweizerische Asylrekurskommission die dagegen erhobene Beschwerde ab, soweit sie darauf eintrat. Am **. ** 1994 verheiratete sich X._ - diesmal unter seinem richtigen Namen und als nigerianischer Staatsangehöriger - in Winterthur mit der 1957 geborenen Schweizer Bürgerin W._. Am 14. Dezember 1994 verurteilte ihn das Bezirksgericht Winterthur wegen mehrfacher Urkundenfälschung zu 16 Monaten Gefängnis bedingt. Mit Verfügung vom 1. Juni 1995 verwarnte ihn die Fremdenpolizei des Kantons Zürich deswegen. Mit Bericht vom 26. Oktober 1997 teilte die Stadtpolizei Winterthur der Fremdenpolizei des Kantons Zürich mit, dass der Freund von W._ anlässlich einer Befragung angegeben habe, diese wohne schon seit Oktober 1995 bei ihm, und es handle sich bei der Beziehung zu ihrem Ehemann um eine Scheinehe. Am 20. August 1998 erklärte W._ gegenüber der Kantonspolizei Zürich, ihre Ehe bestehe seit dem August 1994 nur noch auf dem Papier; X._ lebe mit seiner Freundin Y._ in Zürich. Mit Schreiben vom 10. Juli 1998 liess X._ der Fremdenpolizei mitteilen, es bestehe keine Absicht, das eheliche Zusammenleben je wieder aufzunehmen, und beim Bezirksgericht Winterthur sei das Ehescheidungsverfahren hängig. Am 20. Januar 1999 wurde X._ die Niederlassungsbewilligung erteilt. Mit Urteil vom 21. Mai 1999 schied das Bezirksgericht Winterthur die Ehe zwischen X._ und W._. Am 20. Januar 1999 wurde X._ die Niederlassungsbewilligung erteilt. Mit Urteil vom 21. Mai 1999 schied das Bezirksgericht Winterthur die Ehe zwischen X._ und W._. B. Am 11. Mai 1999 nahm die Kantonspolizei Zürich X._ wegen Verdachts auf Betäubungsmittelhandel fest; die Zeit vom 14. Mai 1999 bis zum 21. März 2000 verbrachte er in Untersuchungshaft. Am 21. Juni 2000 verurteilte ihn das Bezirksgericht A._ wegen Widerhandlungen gegen das Betäubungsmittelgesetz zu einer Zuchthausstrafe von sechs Jahren. Es ordnete zudem den Vollzug der am 14. Dezember 1994 bedingt ausgesprochenen Gefängnisstrafe von 16 Monaten an. Mit Urteil vom 29. Januar 2001 reduzierte das Obergericht des Kantons Zürich das Strafmass auf vier Jahre Zuchthaus, bestätigte hingegen den Widerruf der bedingt ausgesprochenen Gefängnisstrafe von 16 Monaten. Die dagegen erhobene Nichtigkeitsbeschwerde wies das Kassationsgericht des Kantons Zürich am 23. November 2001 ab. Mit Verfügung vom 7. August 2002 entliess der Justizvollzug des Kantons Zürich X._ auf den 5. September 2002 bedingt aus dem Strafvollzug. Mit Verfügung vom 7. August 2002 entliess der Justizvollzug des Kantons Zürich X._ auf den 5. September 2002 bedingt aus dem Strafvollzug. C. Mit Beschluss vom 11. Dezember 2002 wies der Regierungsrat des Kantons Zürich X._ für die Dauer von zehn Jahren aus der Schweiz aus. Gegen diesen Beschluss erhoben X._ sowie seine Lebenspartnerin Y._ am 5. Februar 2003 Beschwerde beim Verwaltungsgericht des Kantons Zürich. Mit Entscheid vom 14. Mai 2003 trat das Verwaltungsgericht des Kantons Zürich auf die Beschwerde von Y._ nicht ein; die Beschwerde von X._ wies es ab, soweit es darauf eintrat. C. Mit Beschluss vom 11. Dezember 2002 wies der Regierungsrat des Kantons Zürich X._ für die Dauer von zehn Jahren aus der Schweiz aus. Gegen diesen Beschluss erhoben X._ sowie seine Lebenspartnerin Y._ am 5. Februar 2003 Beschwerde beim Verwaltungsgericht des Kantons Zürich. Mit Entscheid vom 14. Mai 2003 trat das Verwaltungsgericht des Kantons Zürich auf die Beschwerde von Y._ nicht ein; die Beschwerde von X._ wies es ab, soweit es darauf eintrat. D. Dagegen haben X._ und Y._ beim Bundesgericht Verwaltungsgerichtsbeschwerde erhoben. Sie beantragen, den Entscheid des Verwaltungsgerichts aufzuheben und von einer Ausweisung von X._ abzusehen, eventualiter dessen Ausweisung auf zwei Jahre zu beschränken. Sie ersuchen zudem um unentgeltliche Rechtspflege und Verbeiständung. Der Regierungsrat des Kantons Zürich hat sich nicht vernehmen lassen. Das Verwaltungsgericht des Kantons Zürich beantragt, die Beschwerde abzuweisen, soweit darauf einzutreten sei. Das Bundesamt für Zuwanderung, Integration und Auswanderung schliesst auf Abweisung der Beschwerde.