Sachverhalt: A. A.a. X._ (Arbeitnehmer, Kläger, Beschwerdeführer) war seit 1998 bei der Y._ AG (Arbeitgeberin, Beklagte, Beschwerdegegnerin) als Produktionsmitarbeiter angestellt. Ab dem 18. Oktober 2011 war der Arbeitnehmer von Dr. A._ immer wieder für unterschiedlich lange Zeit zu 100 % arbeitsunfähig geschrieben, so vom 18. Oktober bis 6. November 2011, vom 9. November bis 4. Dezember 2011 und vom 25. Januar bis 5. Februar 2012. A.b. Am 16. Februar 2012 wurde der Arbeitnehmer vom Produktionsleiter der Arbeitgeberin aufgefordert, für einen dringend fertig zu stellenden Auftrag Mehrarbeit zu leisten. Der Arbeitnehmer verweigerte die Mehrarbeit, da er nach eigenen Angaben eigentlich gar nicht arbeitsfähig gewesen sei und sich selbst für die Leistung von 100 % "durchgebissen" habe. Es kam zu einem Wortwechsel zwischen dem Arbeitnehmer und dem Produktionsleiter bzw. dem Geschäftsführer der Arbeitgeberin, woraufhin dem Arbeitnehmer die Kündigung ausgehändigt wurde. Ein ärztliches Attest, welches die Arbeitsunfähigkeit des Arbeitnehmers am 16. Februar 2012 bescheinigt hätte, lag nicht vor. Der Arbeitnehmer macht geltend, die gegen ihn ausgesprochene Kündigung sei missbräuchlich. B. B.a. Mit Klage vom 19. Juni 2012 beantragte der Arbeitnehmer dem Kantonsgericht von Appenzell Ausserrhoden, die Arbeitgeberin sei zu verpflichten, ihm den Betrag von Fr. 15'762.50 nebst Zins zu bezahlen und es sei vom Nachklagerecht Vormerk zu nehmen. Die Beklagte beantragte die Abweisung der Klage und machte widerklageweise geltend, es sei festzustellen, dass sie dem Kläger nichts schulde. Mit Entscheid vom 11. Februar 2013 wies das Kantonsgericht von Appenzell Ausserrhoden die Klage ab. In Gutheissung der Widerklage stellte es fest, dass die Beklagte dem Kläger aus dem Arbeitsverhältnis nichts mehr schulde. B.b. Gegen diesen Entscheid erhob der Kläger Berufung an das Obergericht Appenzell Ausserrhoden, welches die Berufung mit Entscheid vom 1. Juli 2013 abwies. C. Mit Beschwerde in Zivilsachen beantragt der Kläger dem Bundesgericht, der Entscheid des Obergerichts Appenzell Ausserrhoden vom 1. Juli 2013 sei aufzuheben und die Klage gutzuheissen. Die negative Feststellungswiderklage der Beklagten sei abzuweisen, sofern überhaupt darauf eingetreten werden könne. Eventualiter sei die Streitsache zur Durchführung weiterer Abklärungen an die Vorinstanz zurückzuweisen. Ferner beantragt der Kläger, es sei von seinem Nachklagerecht Vormerk zu nehmen. Die Beschwerdegegnerin beantragt die Abweisung der Beschwerde, soweit darauf einzutreten sei. Die Vorinstanz hat auf eine Vernehmlassung verzichtet. Der Beschwerdeführer hat unaufgefordert eine Replik, die Beschwerdegegnerin eine Duplik eingereicht. D. Mit Präsidialverfügung vom 23. September 2013 wurde der Beschwerde die aufschiebende Wirkung erteilt.