Sachverhalt: A. A._ (Kläger, Beschwerdeführer) erhielt im Frühjahr 2007 von seinem Onkel B._ ein handschriftliches, vom 20. Juni 2004 datiertes Testament ausgehändigt, in dem B._ ihn als Alleinerben seiner Liegenschaft Q._ in J._l einsetzte. Daraufhin setzte sich A._ mit seiner Treuhänderin, der X._ Treuhand AG (Beklagte, Beschwerdegegnerin), in Verbindung, um das Testament prüfen zu lassen. Dazu übermittelte er ihr das Testament per Fax. Am 4. Mai 2007 erteilte die X._ Treuhand AG A._ schriftlich den Rat, im Testament noch sein Geburtsdatum einzufügen, den Erblasser mit seinem Geburtsnamen (statt mit dem Rufnamen) unterzeichnen zu lassen sowie noch einen Widerruf allfälliger früherer letztwilliger Verfügungen aufzunehmen. Gestützt darauf fügte der Erblasser in das Original der Urkunde handschriftlich das Geburtsdatum von A._ ein und unterzeichnete es nochmals mit dem Vornamen; auf eine weitere Ergänzung wurde verzichtet. Die X._ Treuhand AG sah das Testament nach diesen Änderungen nicht mehr. Nach dem Tod von B._ im August 2007 wurde das Testament in dieser Form eingereicht. Dieses wurde in der Folge erfolgreich wegen Nichteinhaltung der Eigenhändigkeitsvorschrift angefochten. A._ anerkannte im Januar 2008 gegenüber den gesetzlichen Erben, dass das Testament nicht in der Handschrift von B._ geschrieben, sondern nur von diesem unterschrieben war. B. Am 1. Dezember 2010 reichte A._ beim Bezirksgericht Dietikon Klage gegen die X._ Treuhand AG ein mit dem Begehren, die X._ Treuhand AG sei zu verpflichten, ihm Schadenersatz in der Höhe von Fr. 277'880.-- nebst Zins, entsprechend dem Wert des ihm wegen der Testamentsungültigkeit entgangenen Erbes, zu bezahlen. Mit Entscheid vom 19. Dezember 2012 wies das Bezirksgericht Dietikon die Klage ab (Ziffer 1), auferlegte die Gerichtskosten in der Höhe von Fr. 15'900.-- dem Kläger (Ziffern 2 und 3) und verpflichtete ihn, der Beklagten eine Prozessentschädigung in der Höhe von Fr. 28'800.-- auszurichten (Ziffer 4). Gegen dieses Urteil erhob der Kläger Berufung an das Obergericht des Kantons Zürich. Dieses erklärte die Berufung des Klägers mit Urteil vom 15. März 2013 als unbegründet und wies die Klage ab (Ziffer 1). Es bestätigte die erstinstanzlichen Kosten- und Entschädigungsfolgen und auferlegte dem Kläger die Gerichtskosten für das zweitinstanzliche Verfahren in der Höhe von Fr. 10'000.-- (Ziffern 2-4). Eine Parteientschädigung für das Berufungsverfahren wurde nicht zugesprochen (Ziffer 5). C. Mit Beschwerde in Zivilsachen beantragt der Kläger dem Bundesgericht, die Dispositiv-Ziffern 1-5 des Urteils des Obergerichts des Kantons Zürich vom 15. März 2013 seien aufzuheben und die Beklagte sei zu verpflichten, dem Kläger Fr. 277'880.-- nebst 5 % Zins seit dem 16. August 2007 zu bezahlen. Eventualiter sei die Streitsache an die Vorinstanz oder das Bezirksgericht Dietikon zurückzuweisen. Die Beklagte beantragt die Abweisung der Beschwerde, soweit darauf einzutreten sei. Die Vorinstanz hat auf eine Vernehmlassung verzichtet. D. Mit Präsidialverfügung vom 6. Juni 2013 wurde das Gesuch des Beschwerdeführers um Gewährung der aufschiebenden Wirkung abgewiesen.