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.

Erwägungen:
1.
1.1. Das Bundesgericht prüft von Amtes wegen und mit freier Kognition, ob ein Rechtsmittel zulässig ist (<ref-law>; <ref-ruling> E. 2; <ref-ruling> E. 1; je mit Hinweisen).
1.2. Die Beschwerde in Zivilsachen ist zulässig gegen Endentscheide, mithin solche, die das Verfahren abschliessen (<ref-law>). Befindet die obere kantonale Instanz über einen Zwischenentscheid einer unteren Instanz, so stellt der Rechtsmittelentscheid regelmässig ebenfalls einen Zwischenentscheid dar: Mit einem solchen Entscheid wird nicht über ein Rechtsverhältnis endgültig entschieden, sondern nur über einen Schritt auf dem Weg zum Endentscheid. Anders ist lediglich dann zu entscheiden, wenn durch den Entscheid der letzten kantonalen Instanz ein Zwischenentscheid der ersten Instanz umgestossen und das Verfahren damit abgeschlossen wird (<ref-ruling> E. 3.2 mit Hinweisen).
Die Erstinstanz stellte in ihrem Vorurteil fest, dass die Beschwerdegegnerin gegenüber dem Beschwerdeführer grundsätzlich genugtuungspflichtig sei. Sie bejahte sowohl den Werkmangel als auch das Vorliegen einer schweren Verletzung der Persönlichkeit sowie die natürliche und adäquate Kausalität zwischen Werkmangel und Persönlichkeitsverletzung, ohne sich einstweilen zur konkreten Schwere dieser Persönlichkeitsverletzung oder zur Höhe der Genugtuung zu äussern. Im angefochtenen Entscheid bestätigte die Vorinstanz den erstinstanzlichen Zwischenentscheid nicht, sondern hiess vielmehr die Berufung der Beschwerdegegnerin gut und wies die Klage des Beschwerdeführers ab. Der vorliegend angefochtene Entscheid schloss damit das Verfahren ab. Es handelt sich demnach um einen Endentscheid im Sinne von <ref-law>.
1.3. Die Beschwerdeschrift hat ein Rechtsbegehren zu enthalten (<ref-law>). Da die Beschwerde in Zivilsachen ein reformatorisches Rechtsmittel ist (<ref-law>), darf sich die beschwerdeführende Partei grundsätzlich nicht darauf beschränken, die Aufhebung des angefochtenen Entscheids zu beantragen, sondern sie muss einen Antrag in der Sache stellen. Anträge auf Rückweisung der Sache an die Vorinstanz zu neuer Entscheidung oder blosse Aufhebungsanträge genügen nicht und machen die Beschwerde unzulässig (<ref-ruling> E. 3.1). Namentlich müssen Rechtsbegehren, die auf einen Geldbetrag lauten, beziffert werden (<ref-ruling> E. 2 mit Hinweis). Ein blosser Rückweisungsantrag reicht ausnahmsweise aus, wenn das Bundesgericht im Falle der Gutheissung nicht selbst in der Sache entscheiden könnte (<ref-ruling> E. 1.2; <ref-ruling> E. 1.3 S. 383; <ref-ruling> E. 3.1).
Die Vorinstanz ist zum Schluss gekommen, dass es dem Beschwerdeführer nicht gelungen sei zu beweisen, dass er beim Betreten des Lager- und Lüftungsraums in der Liegenschaft der Beschwerdegegnerin gestürzt sei. Da sich der vom Beschwerdeführer geltend gemachte Werkmangel beim Eingang zu diesem Raum befinde, falle das Fundament seiner Klage dahin und die Klage sei demnach abzuweisen. Abgesehen davon hat die Vorinstanz zu den Voraussetzungen des Genugtuungsanspruchs keine tatsächlichen Feststellungen getroffen. Sollte das Bundesgericht die Rechtsauffassung des Beschwerdeführers, wonach ein Genugtuungsanspruch gegenüber der Beschwerdegegnerin grundsätzlich bestehe, als begründet erachten, könnte es daher keinen Entscheid in der Sache fällen, sondern müsste die Streitsache an die Vorinstanz zurückweisen. Bei dieser Sachlage genügt der blosse Rückweisungsantrag des Beschwerdeführers.
1.4. Da auch die übrigen Sachurteilsvoraussetzungen erfüllt sind, ist auf die Beschwerde unter Vorbehalt einer hinreichenden Begründung (Art. 42 Abs. 2 und <ref-law>) einzutreten.
2.
2.1. Mit Beschwerde in Zivilsachen können Rechtsverletzungen nach Art. 95 und 96 BGG gerügt werden. Die Beschwerde ist hinreichend zu begründen, andernfalls wird darauf nicht eingetreten (<ref-ruling> E. 2.1). In der Beschwerdeschrift ist in gedrängter Form darzulegen, inwiefern der angefochtene Akt Recht verletzt (<ref-law>). Unerlässlich ist, dass die Beschwerde auf die Begründung des angefochtenen Entscheids eingeht und im Einzelnen aufzeigt, worin eine Verletzung von Bundesrecht liegt. Die beschwerdeführende Partei soll in der Beschwerdeschrift nicht bloss die Rechtsstandpunkte, die sie im kantonalen Verfahren eingenommen hat, erneut bekräftigen, sondern mit ihrer Kritik an den als rechtsfehlerhaft erachteten Erwägungen der Vorinstanz ansetzen (<ref-ruling> E. 2 S. 89, 115 E. 2 S. 116). Eine qualifizierte Rügepflicht gilt hinsichtlich der Verletzung von Grundrechten und von kantonalem und interkantonalem Recht. Das Bundesgericht prüft eine solche Rüge nur insofern, als sie in der Beschwerde präzise vorgebracht und begründet worden ist (<ref-law>; <ref-ruling> E. 1.4; <ref-ruling> E. 1.3.1). Soweit die Beschwerdeschrift diesen Begründungsanforderungen nicht genügt, so ist darauf nicht einzutreten (BGE <ref-ruling> E. 1.3.1).
Das Bundesgericht greift in die Beweiswürdigung des Sachgerichts sodann nur ein, wenn diese willkürlich ist. Willkür liegt nicht schon dann vor, wenn eine andere Lösung ebenfalls in Betracht zu ziehen oder gar vorzuziehen wäre, sondern nur, wenn der angefochtene Entscheid offensichtlich unhaltbar ist, mit der tatsächlichen Situation in klarem Widerspruch steht, eine Norm oder einen unumstrittenen Rechtsgrundsatz krass verletzt oder in stossender Weise dem Gerechtigkeitsgedanken zuwiderläuft (<ref-ruling> E. 2.1; <ref-ruling> E. 5.1 S. 22; <ref-ruling> E. 4.1; <ref-ruling> E. 2.1). Dies ist dann der Fall, wenn das Gericht Sinn und Tragweite eines Beweismittels offensichtlich verkannt hat, wenn es ohne sachlichen Grund ein wichtiges und entscheidwesentliches Beweismittel unberücksichtigt gelassen oder wenn es auf der Grundlage der festgestellten Tatsachen unhaltbare Schlussfolgerungen gezogen hat (<ref-ruling> E. 2.3 S. 266; <ref-ruling> E. 4.2 S. 234; <ref-ruling> E. 4.2). Inwiefern die Beweiswürdigung willkürlich sein soll, ist in der Beschwerde klar und detailliert aufzuzeigen (<ref-ruling> E. 2.2; <ref-ruling> E. 1.3 S. 262).
2.2. Die Beschwerde ist innert der Beschwerdefrist vollständig begründet einzureichen (vgl. <ref-law>). Vor Bundesgericht findet in der Regel nur ein Schriftenwechsel statt (<ref-law>). Kommt es zu einem zweiten Schriftenwechsel, darf die beschwerdeführende Partei die Replik nicht dazu verwenden, ihre Beschwerde zu ergänzen oder zu verbessern (<ref-ruling> E. 1.7; <ref-ruling> E. 3.3.4). Mit Rügen, welche die beschwerdeführende Partei bereits in der Beschwerde hätte erheben können, ist sie nach Ablauf der Beschwerdefrist ausgeschlossen (<ref-ruling> E. 2.2; <ref-ruling> E. 1.7; <ref-ruling> E. 3.3.4 mit Hinweisen). Die Replik ist nur zu Darlegungen zu verwenden, zu denen die Ausführungen in der Vernehmlassung eines anderen Verfahrensbeteiligten Anlass geben (vgl. <ref-ruling> E. 2.2). Soweit der Beschwerdeführer in seiner Replik darüber hinausgeht, kann er nicht gehört werden.
2.3. Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (<ref-law>). Dazu gehören sowohl die Feststellungen über den Lebenssachverhalt, der dem Streitgegenstand zugrunde liegt, als auch jene über den Ablauf des vor- und erstinstanzlichen Verfahrens, also die Feststellungen über den Prozesssachverhalt (<ref-ruling> E. 1.3.1). Das Bundesgericht kann die Sachverhaltsfeststellung der Vorinstanz nur berichtigen oder ergänzen, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht (<ref-law>). "Offensichtlich unrichtig" bedeutet dabei "willkürlich" (<ref-ruling> E. 2 S. 117; <ref-ruling> E. 1.5). Entsprechende Rügen sind überdies bloss zulässig, wenn die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (<ref-law>).
3.
Anders als die Erstinstanz hielt die Vorinstanz die Darstellung des Beschwerdeführers über den Unfallhergang für nicht erstellt. Sie erwog, der Beschwerdeführer habe seine Klage am 22. Dezember 2010 bei der Erstinstanz anhängig gemacht und damit noch vor Inkrafttreten der Schweizerischen Zivilprozessordnung (ZPO; SR 272). Auf das Verfahren vor der Erstinstanz komme daher die kantonalzürcherische Zivilprozessordnung vom 13. Juni 1976 (ZPO/ZH; LS 271) zur Anwendung, während das Berufungsverfahren grundsätzlich der Schweizerischen Zivilprozessordnung unterstehe (<ref-law>). Die Überprüfung eines nach altem Recht ergangenen Entscheids auf Verfahrensverstösse erfolge jedoch nach bisherigem Recht. Nach <ref-law>/ZH würden Aussagen einer Partei in der Parteibefragung zu ihren eigenen Gunsten keinen Beweis bilden. Damit könne die Aussage des Beschwerdeführers in der Parteibefragung in diesem Verfahren nicht als Beweismittel zur Sachverhaltserstellung herangezogen werden. Dementsprechend würde entgegen der Ansicht der Erstinstanz auch die Berücksichtigung dieser Aussagen bei der Beurteilung der Glaubwürdigkeit von Zeugen und der Glaubhaftigkeit von deren Aussagen sowie zur Beurteilung des Beweiswerts von Urkunden zumindest insoweit ausser Betracht fallen, als sie sich zugunsten des Beschwerdeführers auswirken würden. Urkunden, die einzig auf den Angaben des Beschwerdeführers beruhten, seien zwar grundsätzlich als Beweismittel verwertbar. Allerdings sei einschränkend anzumerken, dass daraus nur hervorgehe, wie die Darstellung des Beschwerdeführers zur Zeit der Erstellung dieser Urkunde laute. Hingegen handle es sich nicht um eine unabhängige Bestätigung des Standpunkts des Beschwerdeführers durch einen Dritten.
Wie die Erstinstanz einleitend zur Beweiswürdigung erwäge, so die Vorinstanz weiter, habe mit Ausnahme des Beschwerdeführers niemand den Unfallhergang wahrgenommen. Die Vorinstanz nahm anschliessend eine Beweiswürdigung der Zeugenaussagen und der schriftlichen Darstellungen des Unfallhergangs vor und kam zum Schluss, dass es dem Beschwerdeführer nicht gelungen sei zu beweisen, dass er beim Betreten des Lager- und Lüftungsraums in der Liegenschaft der Beschwerdegegnerin gestürzt sei. Da sich der vom Beschwerdeführer geltend gemachte Werkmangel beim Eingang zum Lager- und Lüftungsraum befinde, falle das Fundament seiner Klage dahin und seine Klage sei demnach abzuweisen.
4.
4.1. Der Beschwerdeführer macht dagegen zunächst geltend, die Beschwerdegegnerin habe nicht bestritten, dass er beim Eingang zum Lager- und Lüftungsraum gestürzt sei bzw. dass sich der Unfall dort zugetragen habe. Damit gelte diese Tatsache als unbestritten und müsse nicht bewiesen werden. Indem die Vorinstanz von den unbestrittenen Sachvorbringen des Beschwerdeführers abweiche, missachte sie die Verhandlungsmaxime und habe damit <ref-law>/ZH willkürlich angewandt bzw. <ref-law> verletzt.
4.2. Zunächst ist zu klären, nach welchem Verfahrensrecht (schweizerische oder zürcherische Zivilprozessordnung) die Vorinstanz die aufgeworfene prozessuale Frage zu beurteilen hatte.
Der Beschwerdeführer machte seine Klage am 22. Dezember 2010 bei der Erstinstanz rechtshängig und damit vor dem Inkrafttreten der Schweizerischen Zivilprozessordnung am 1. Januar 2011. Auf das erstinstanzliche Verfahren fand damit noch die kantonale Zürcher Zivilprozessordnung Anwendung (<ref-law>). Da der erstinstanzliche Entscheid vom 31. März 2015 den Parteien nach Inkrafttreten der ZPO eröffnet wurde, waren für das Rechtsmittelverfahren vor der Vorinstanz grundsätzlich die Bestimmungen der inzwischen in Kraft getretenen ZPO massgebend (<ref-law>). Soweit es aber um prozessuale Fragen des erstinstanzlichen Verfahrens geht, hat die Rechtsmittelinstanz die richtige Anwendung des bisherigen kantonalen Verfahrensrechts zu prüfen (<ref-ruling> E. 2.1 S. 3; <ref-ruling> E. 2.1) und entsprechend seinem Urteil das im erstinstanzlichen Entscheid noch massgebliche kantonale Prozessrecht zu Grunde zu legen (Urteile 4A_85/2014 vom 16. Juni 2014 E. 3.2.1; 4A_383/2013 vom 2. Dezember 2013 E. 4.2.3).
Die prozessuale Frage, ob die Beschwerdegegnerin den behaupteten Unfallhergang, insbesondere den Unfallort, bestritten hat oder nicht, beurteilt sich demnach nach der zürcherischen Zivilprozessordnung.
4.3. Geht es um kantonales Prozessrecht kann - von hier nicht zutreffenden Ausnahmen abgesehen (Art. 95 lit. c-e BGG) - vor Bundesgericht nur Willkür (<ref-law>) gerügt werden. Dabei ist die kantonale Bestimmung, die qualifiziert unrichtig angewendet bzw. nicht angewendet worden sein soll, zu bezeichnen und anhand der angefochtenen Subsumtion im Einzelnen zu zeigen, inwiefern der Entscheid offensichtlich unhaltbar ist, mit der tatsächlichen Situation in klarem und offensichtlichem Widerspruch steht, eine Norm oder einen unumstrittenen Rechtsgrundsatz krass verletzt oder in stossender Weise dem Gerechtigkeitsgedanken zuwiderläuft (<ref-law>; <ref-ruling> E. 2.1 S. 3; Urteil 5A_351/2015 vom 1. Dezember 2015 E. 2.3).
4.4. Der Beschwerdeführer vermag nicht aufzuzeigen, dass die Vorinstanz die Verhandlungsmaxime nach <ref-law>/ZH willkürlich angewandt hätte. Es mag zwar zutreffen, dass sie nicht ausdrücklich erwog, dass die Beschwerdegegnerin den Unfallort bestritten habe. Sie ging jedoch implizit von einer rechtsgenüglichen Bestreitung der Beschwerdegegnerin aus, indem sie eine Beweiswürdigung über den Unfallort vornahm. Wie die Beschwerdegegnerin sodann in ihrer Beschwerdeantwort zu Recht ausführt, hat sie in der erstinstanzlichen Duplik vom 7. November 2011 vorgebracht, dass sie "an ihrer Bestreitung fest[halte], dass sich am 2. Mai 2007 im fraglichen Kellerraum bzw. auf dessen Zugang der vom [Beschwerdeführer] beschriebene Unfall ereignet habe". Im Weiteren hat sie in der genannten Duplik erklärt, dass sie "an der Bestreitung eines Unfalls auf dem Zugang zum Lagerraum" festhalte. Die Beschwerdegegnerin hat somit an diesen Stellen in der Duplik durchaus bestritten, dass sich der Unfall an sich und am fraglichen Ort ereignet habe. Inwiefern es willkürlich sein soll, wenn die Vorinstanz gestützt auf diese Ausführungen davon ausging, dass die Beschwerdegegnerin hinreichend bestritten habe, dass sich der Unfall an der genannten Stelle ereignet habe, also dass der Beschwerdeführer dort gestürzt sei, und so von einem bestrittenen Unfallort bezüglich dem Lager- und Lüftungsraum im Keller der Liegenschaft der Beschwerdegegnerin bzw. auf dessen Zugang ausging, vermag der Beschwerdeführer nicht darzulegen.
4.5. Der Beschwerdeführer rügt schliesslich für den Fall, dass das Bundesgericht zum Schluss komme, dass bezüglich der Verhandlungsmaxime keine willkürliche Verletzung des kantonalen Verfahrensrechts vorliege, eine Verletzung von <ref-law>. Die Vorinstanz habe mit keinem Wort seine persönliche Befragung gewürdigt, obschon die Erstinstanz diese Schilderungen als sehr glaubhaft bezeichnet habe. Sodann habe sie die in den Urkunden festgehaltenen Aussagen, die auf seinen Angaben beruhten, unter dem Blickwinkel von <ref-law>/ZH gewürdigt. Wenn die Vorinstanz seine persönliche Aussage völlig ausser Acht lasse und nicht alle zur Verfügung stehenden Beweise würdige, habe sie sich im Berufungsverfahren fälschlicherweise den Beweisbeschränkungen der früheren kantonalen Zivilprozessordnung nach <ref-law>/ZH unterworfen und keine freie Beweiswürdigung vorgenommen.
4.6. Diese Rüge des Beschwerdeführers ist nicht zielführend, denn auch bei Zugrundelegung von <ref-law> (freie Beweiswürdigung) vermag der Beschwerdeführer nicht darzulegen, inwiefern die vorinstanzliche Beweiswürdigung willkürlich wäre (vgl. Erwägung 2.1).
Es mag zwar zutreffen, dass sich die Vorinstanz nicht ausdrücklich mit den Aussagen des Beschwerdeführers auseinandersetzte. Sie erwog jedoch, dass nicht ausgeschlossen werden könne, dass der Beschwerdeführer den Unfallhergang beispielsweise in Bezug auf den Unfallort anders schildere, um sich eine vorteilhaftere Ausgangslage für eine allenfalls bevorstehende Auseinandersetzung mit einer Unfall- und Haftpflichtversicherung zu verschaffen und einer Diskussion über ein allfälliges Selbstverschulden aus dem Weg zu gehen. Daraus geht hervor, dass die Vorinstanz die Aussagen des Beschwerdeführers im erstinstanzlichen Verfahren, zumindest implizit, würdigte und als nicht glaubhaft und widerspruchsfrei ansah. Die Rüge des Beschwerdeführers, dass die Vorinstanz nicht sämtliche Beweise gewürdigt hätte, geht damit fehl.
Sodann erwog die Vorinstanz bezüglich der schriftlichen Darstellungen des Unfallhergangs durch Dritte, die den Unfall nicht selbst wahrgenommen haben, sondern sich einzig auf die Angaben des Beschwerdeführers abstützten, dass es sich hierbei nicht um eine unabhängige Bestätigung des Standpunktes des Beschwerdeführers durch einen Dritten handle, was in der Beweiswürdigung zu berücksichtigen sei. Inwiefern es geradezu unhaltbar sein soll, wenn die Vorinstanz in der Beweiswürdigung diesen Urkunden, die einzig auf den Schilderungen des Beschwerdeführers beruhen, keine entscheidende Beweiskraft beimass, gelingt dem Beschwerdeführer nicht aufzuzeigen.
Schliesslich kann der Beschwerdeführer daraus, dass die Vorinstanz die Beweise anders als die Erstinstanz würdigte, nichts zu seinen Gunsten ableiten.
5.
Nach dem Ausgeführten ist die Beschwerde abzuweisen, soweit auf sie eingetreten werden kann. Bei diesem Ausgang des Verfahrens wird der Beschwerdeführer kosten- und entschädigungspflichtig (Art. 66 Abs. 1 und Art. 68 Abs. 1 BGG).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2.
Die Gerichtskosten von Fr. 2'500.-- werden dem Beschwerdeführer auferlegt.
3.
Der Beschwerdeführer hat die Beschwerdegegnerin für das bundesgerichtliche Verfahren mit Fr. 3'000.-- zu entschädigen.
4.
Dieses Urteil wird den Parteien und dem Obergericht des Kantons Zürich, II. Zivilkammer, schriftlich mitgeteilt.
Lausanne, 24. Juni 2016
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Kiss
Der Gerichtsschreiber: Brugger