Sachverhalt: A. A._ (Kläger, Beschwerdeführer) war Angestellter der C._ AG, die in den Räumen der B._ AG (Beklagte, Beschwerdegegnerin) eingemietet ist. Am 2. Mai 2007 stürzte der Kläger nach seinen Aussagen beim Betreten eines Lager- und Lüftungsraums im Keller dieser Liegenschaft. Dieser Sturz habe laut seiner Darstellung zu einer bleibenden gesundheitlichen Schädigung geführt und er sei seither nur noch zu 50 % sowie nicht mehr in seinem Beruf als Fitnesslehrer arbeitsfähig. B. Am 22. Dezember 2010 machte der Kläger am Bezirksgericht Uster eine Klage gegen die Beklagte anhängig und verlangte, diese sei zu verpflichten, ihm eine Genugtuung von Fr. 50'000.-- nebst Zins zu 5 % seit dem 2. Mai 2007 zu bezahlen (unter Vorbehalt weiterer Schadenersatzforderungen). Er begründete seine Klage damit, dass beim Eingang zum Lagerraum in der Liegenschaft der Beklagten ein Niveauunterschied von 50 cm bestehe, der nur behelfsmässig überbrückt gewesen sei, weshalb die Beklagte als Werkeigentümerin für die Folgen des Unfalls hafte. Am 23. April 2013 erliess das Bezirksgericht einen Beweisauflagebeschluss, wobei es das Beweisverfahren einstweilen auf die Frage beschränkte, ob im Grundsatz ein Genugtuungsanspruch bestehe. Nach Durchführung des Beweisverfahrens fällte das Bezirksgericht am 31. März 2015 ein Vorurteil und kam zum Schluss, dass die Beklagte gegenüber dem Kläger grundsätzlich genugtuungspflichtig sei. Die Beklagte erhob dagegen Berufung an das Obergericht des Kantons Zürich, das mit Urteil vom 14. Dezember 2015 die Berufung guthiess, das Vorurteil des Bezirksgerichts aufhob und die Klage abwies. C. Der Beschwerdeführer beantragt mit Beschwerde in Zivilsachen, der Entscheid des Obergerichts sei aufzuheben und die Streitsache sei an das Obergericht zurückzuweisen zu neuerlichem Entscheid. Die Beschwerdegegnerin beantragt, die Beschwerde sei abzuweisen. Die Vorinstanz verzichtete auf Vernehmlassung. Die Parteien reichten Replik und Duplik ein.