Sachverhalt: A. A._ (Arbeitnehmer, Kläger, Beschwerdeführer) war vom 1. Februar 2009 bis am 31. März 2012 bei der B._ AG (Arbeitgeberin, Beklagte, Beschwerdegegnerin) als CEO Schweiz und Mitglied der Konzernleitung angestellt. Der Arbeitsvertrag vom 24. Oktober 2008 enthielt im Abschnitt "Besondere Vereinbarungen" u.a. folgende Bestimmungen: "Die [Arbeitgeberin] erklärt sich bereit, einen durch Ihre Kündigung bei Ihrem jetzigen Arbeitgeber entfallenden Bonus für 2008 in Höhe von CHF 890'000.00 brutto in Form eines sign-on Bonus zu übernehmen. Die Auszahlung dieses sign-on Bonus erfolgt entlang der gemeinsam festzulegenden Modalitäten. Die [Arbeitgeberin] erklärt sich bereit, einen durch Ihre Kündigung bei Ihrem jetzigen Arbeitgeber entfallenden 'Long term incentive' im Betrag von maximal GBP 360'000.- zu übernehmen. Der Gegenwert in CHF wird zum Zeitpunkt des Beginns des Arbeitsverhältnisses bestimmt und als Einkauf in die Pensionskasse der [Arbeitgeberin] einbezahlt." Mit Austrittsabrechnung per 31. März 2012 zog die Pensionskasse der Arbeitgeberin unter dem Titel "Von der Gesellschaft geleistete Einkaufssumme" Fr. 416'640.-- von der Freizügigkeitsleistung ab; dieser Betrag entspricht sieben Zehntel der Einkaufssumme von GBP 360'000.-- resp. von umgerechnet Fr. 595'200.--. In der Folge konnten sich die Parteien nicht über die Rechtmässigkeit dieses Abzugs einigen. B. Nach erfolglosem Schlichtungsverfahren gelangte der Arbeitnehmer mit Klage vom 1. März 2013 an das Zivilgericht Basel-Stadt. Er verlangte von der Beklagten die Bezahlung von Fr. 416'640.-- nebst Zins (unter Nachklagevorbehalt) unter Kosten- und Entschädigungsfolge. Mit Urteil vom 27. November 2014 wies das Zivilgericht die Klage ab. Die dagegen erhobene Berufung des Klägers wies das Appellationsgericht des Kantons Basel-Stadt mit Urteil vom 21. Dezember 2015 ab. C. Mit Beschwerde in Zivilsachen beantragt der Kläger dem Bundesgericht, das Urteil des Appellationsgerichts sei aufzuheben und die Beklagte sei unter Kostenfolgen zur Zahlung von Fr. 416'640.-- nebst Zins (unter Vorbehalt von Mehrforderungen) zu verpflichten. Eventualiter sei die Streitigkeit zur neuen Entscheidung an das Appellationsgericht zurückzuweisen. Die Beschwerdegegnerin beantragt, die Beschwerde sei kostenfällig abzuweisen, soweit darauf einzutreten sei. Das Appellationsgericht beantragt unter Hinweis auf das angefochtene Urteil die Abweisung, verzichtet im Übrigen aber auf eine Stellungnahme. Die Parteien haben unaufgefordert repliziert bzw. dupliziert.