Sachverhalt: A. S._ (Arbeitnehmer, Kläger, Beschwerdeführer) war seit 2002 als Taxichauffeur bei der X._ AG (Arbeitgeberin, Beklagte, Beschwerdegegnerin) tätig. Mit Schreiben vom 23. August 2010 kündigte die Arbeitgeberin dem Arbeitnehmer das Arbeitsverhältnis unter Einhaltung der gesetzlichen Kündigungsfrist von zwei Monaten auf den 31. Oktober 2010. Im Kündigungsschreiben wurde zur Begründung der Kündigung auf ein Schreiben vom 19. September 2008 verwiesen, in welchem der Arbeitnehmer im Zusammenhang mit einer Transportverweigerung verwarnt wurde, sowie auf verschiedene Meldungen seitens der Disposition, wonach der Arbeitnehmer immer wieder einzelne Fahraufträge verweigert habe. Mit Schreiben vom 27. Oktober 2010 erhob der Arbeitnehmer Einsprache gegen die Kündigung. B. Mit Eingabe vom 1. September 2011 erhob der Arbeitnehmer beim Regionalgericht Bern-Mittelland Klage gegen die Arbeitgeberin, mit dem im Laufe des Verfahrens abgeänderten Begehren, es sei festzustellen, dass die am 23. August 2010 ausgesprochene Kündigung missbräuchlich sei und die Arbeitgeberin sei zu verpflichten, ihm eine Entschädigung infolge missbräuchlicher Kündigung in der Höhe von Fr. 29'999.-- zu bezahlen. Mit Entscheid vom 27. April 2012 trat das Regionalgericht Bern-Mittelland auf das Feststellungsbegehren nicht ein und wies die Klage soweit weitergehend ab. Gegen diesen Entscheid erhob der Kläger Berufung an das Obergericht des Kantons Bern. Dieses wies die Berufung mit Entscheid vom 28. Februar 2013 ab und bestätigte den Entscheid des Regionalgerichts Bern-Mittelland vom 27. April 2012. C. Mit Beschwerde in Zivilsachen beantragt der Kläger dem Bundesgericht, die Beklagte sei zu verpflichten, ihm einen Betrag von Fr. 29'999.-- zu bezahlen. Eventualiter sei der angefochtene Entscheid aufzuheben und zur Zeugeneinvernahme und Neubeurteilung an die Vorinstanz zurückzuweisen. Die Beklage beantragt die Abweisung der Beschwerde, soweit darauf einzutreten sei. Die Vorinstanz hat auf eine Vernehmlassung verzichtet. 