Sachverhalt: Sachverhalt: A. Am 29. Oktober 2003 kündigte die C._ AG den Arbeitsvertrag mit A._ (Beschwerdeführer) per 30. November 2003. Gemäss dem Wortlaut des Kündigungsschreibens erfolgte die Kündigung "wegen der bevorstehenden Beendigung des Mietverhältnisses mit der D._ AG und den damit verbundenen Konsequenzen sowie dem fusionsbedingten Wegfall (des) Hauptkunden E._ AG". Am 2. Dezember 2003 teilte die Einzelfirma B._ (Beschwerdegegnerin) ihren Kunden mit, dass aus Arbeitnehmern der bisherigen Firmen C._ AG und B._ die neue Mannschaft der Beschwerdegegnerin geformt worden sei. Unter diesen Arbeitnehmern befand sich auch der Beschwerdeführer. Mit ihm hatte die Beschwerdegegnerin per 1. Dezember 2003 einen neuen Arbeitsvertrag abgeschlossen. Dieser wurde jedoch innerhalb der Probezeit per 17. Januar 2004 wieder aufgelöst. Im Zusammenhang mit den Ansprüchen, welche der Beschwerdeführer in der Folge gegenüber der Beschwerdegegnerin geltend machte, ist insbesondere umstritten, ob das Arbeitsverhältnis des Beschwerdeführers mit der C._ AG gemäss Art. 333 OR auf die Beschwerdegegnerin übergegangen ist. Am 2. Dezember 2003 teilte die Einzelfirma B._ (Beschwerdegegnerin) ihren Kunden mit, dass aus Arbeitnehmern der bisherigen Firmen C._ AG und B._ die neue Mannschaft der Beschwerdegegnerin geformt worden sei. Unter diesen Arbeitnehmern befand sich auch der Beschwerdeführer. Mit ihm hatte die Beschwerdegegnerin per 1. Dezember 2003 einen neuen Arbeitsvertrag abgeschlossen. Dieser wurde jedoch innerhalb der Probezeit per 17. Januar 2004 wieder aufgelöst. Im Zusammenhang mit den Ansprüchen, welche der Beschwerdeführer in der Folge gegenüber der Beschwerdegegnerin geltend machte, ist insbesondere umstritten, ob das Arbeitsverhältnis des Beschwerdeführers mit der C._ AG gemäss Art. 333 OR auf die Beschwerdegegnerin übergegangen ist. B. Das Gewerbliche Schiedsgericht des Zivilgerichts Basel-Stadt hat am 5. April 2004 die Zulässigkeit der Kündigung des zwischen der C._ AG und dem Beschwerdeführer abgeschlossenen Arbeitsvertrages bejaht. Zufolge gültiger Kündigung könne daher von einem Übergang des Arbeitsverhältnisses auf die Beschwerdegegnerin als Erwerberin des Betriebes keine Rede sein. Vielmehr habe die Beschwerdegegnerin mit dem Beschwerdeführer einen neuen Vertrag mit einer Probezeit abgeschlossen. Aus dem neu abgeschlossenen Arbeitsvertrag stehe dem Beschwerdeführer keine Forderungen zu, so dass die Klage abzuweisen sei. Dieser Entscheid wurde vom Beschwerdeführer beim Appellationsgericht des Kantons Basel-Stadt angefochten. Dabei beantragte der Beschwerdeführer im Wesentlichen, in Gutheissung seiner Klage sei die Beschwerdegegnerin zu verpflichten, ihm Fr. 3'515.85 zuzüglich Zins zu bezahlen. Mit Urteil vom 26. August 2004 wies das Appellationsgericht die Beschwerde ab. B. Das Gewerbliche Schiedsgericht des Zivilgerichts Basel-Stadt hat am 5. April 2004 die Zulässigkeit der Kündigung des zwischen der C._ AG und dem Beschwerdeführer abgeschlossenen Arbeitsvertrages bejaht. Zufolge gültiger Kündigung könne daher von einem Übergang des Arbeitsverhältnisses auf die Beschwerdegegnerin als Erwerberin des Betriebes keine Rede sein. Vielmehr habe die Beschwerdegegnerin mit dem Beschwerdeführer einen neuen Vertrag mit einer Probezeit abgeschlossen. Aus dem neu abgeschlossenen Arbeitsvertrag stehe dem Beschwerdeführer keine Forderungen zu, so dass die Klage abzuweisen sei. Dieser Entscheid wurde vom Beschwerdeführer beim Appellationsgericht des Kantons Basel-Stadt angefochten. Dabei beantragte der Beschwerdeführer im Wesentlichen, in Gutheissung seiner Klage sei die Beschwerdegegnerin zu verpflichten, ihm Fr. 3'515.85 zuzüglich Zins zu bezahlen. Mit Urteil vom 26. August 2004 wies das Appellationsgericht die Beschwerde ab. C. Mit staatsrechtlicher Beschwerde vom 10. Dezember 2004 beantragt der Beschwerdeführer dem Bundesgericht, das Urteil des Appellationsgerichts Basel-Stadt vom 26. August 2004 sei aufzuheben. Die Beschwerdegegnerin beantragt, die staatsrechtliche Beschwerde sei abzuweisen, soweit darauf einzutreten sei. Das Appellationsgericht schliesst auf Abweisung der Beschwerde.