Sachverhalt: A. A.a. Die B._ AG bzw. deren Rechtsvorgängerin (Vermieterin, Klägerin, Beschwerdegegnerin) überliess mit Vertrag vom 27. August 2002 der A._ AG (Mieterin, Beklagte, Beschwerdeführerin) Geschäftsräume im ersten Stock der Liegenschaft an der C._gasse yyy in Basel zur Nutzung. A.b. Die Mieterin betreibt in den Mieträumlichkeiten ein Fitnesscenter. Der Vertrag sieht eine zehnjährige Laufzeit und Option der Mieterin auf Verlängerung um weitere fünf Jahre vor. Der jährliche Mietzins wurde für die ersten beiden Jahre auf mindestens Fr. 150'000.-- und ab dem dritten Jahr auf Fr. 200'000.-- festgesetzt. Zuvor hatte die Rechtsvorgängerin der Vermieterin ab Januar 2000 einen Mietvertrag für 25 Jahre abgeschlossen und einen gestaffelten Mietzins zwischen Fr. 267'000.-- für das erste und Fr. 445'000.-- ab dem vierten Jahr vereinbart. Die frühere Mieterin hatte das Mietobjekt mit wesentlicher Beteiligung der Vermieterin zum Fitnesscenter umgebaut; der Betrieb entwickelte sich jedoch nicht wie erwartet, weshalb sich die damaligen Mietvertragsparteien auf die vorzeitige Vertragsauflösung einigten. A.c. Die Mieterin nahm im Oktober 2002 ihren Betrieb in den Mieträumlichkeiten auf. Ab November 2010 mietete sie zusätzliche Lagerflächen. Mit Schreiben vom 29. März 2011 übte sie die Option aus und verlängerte den Vertrag damit bis Ende September 2017. A.d. Mit Abrechnung vom 16. Januar 2012 stellte die Vermieterin der Mieterin die Nebenkostenabrechnung für das Jahr 2010 zu. Die Mieterin verweigerte die Zahlung und bezahlte ab März 2012 auch die Mietzinsen nicht mehr, worauf die Vermieterin sie unter Kündigungsandrohung abmahnte. Die Mieterin erklärte darauf Verrechnung mit einer Gegenforderung von Fr. 833'129.14. Sie begründete die Gegenforderung mit Rückforderungen aus rechtswidriger Kombination von Staffel- und Indexmieten sowie einer rechtswidrigen Überbindung von Unterhaltspflichten; ausserdem rügte sie in weiteren Schreiben verschiedene Mängel am Mietobjekt. B. B.a. Am 21. Januar 2013 gelangte die Vermieterin an die zuständige Schlichtungsstelle für Mietstreitigkeiten mit dem Begehren, die Mieterin sei zu verurteilen, Mietzinsen und Nebenkosten von Fr. 321'220.71 nebst 5% Zins seit 1. Oktober 2012 zu bezahlen. Mit Entscheid vom 24. September 2014 verurteilte das Zivilgericht des Kantons Basel-Stadt die Mieterin dazu, der Vermieterin Fr. 318'289.05 nebst 5% Zins seit 1. Oktober 2012 zu bezahlen. Das Zivilgericht stellte fest, dass die Höhe des Mietzinsausstandes für die Zeit vom 1. März 2012 bis 31. März 2013 im Betrag von Fr. 289'469.31 (13 x Fr. 22'266.87) unbestritten sei; die von der Klägerin für das Jahr 2010 geforderten Nebenkosten von Fr. 31'751.40 erkannte es im Umfang von Fr. 2'780.85 für unberechtigt. Zu den Gegenforderungen, welche die Mieterin im Prozess mit Fr. 1'995'000.-- bezifferte, hielt das Zivilgericht vorweg fest, dass diese die Nettomietzinsen für die gesamte Mietdauer übersteigen würden. Im einzelnen hielt das Zivilgericht die Rückforderung der im Laufe der Mietdauer übernommenen Unterhalts- und Instandstellungskosten von insgesamt Fr. 520'336.90 für unberechtigt mit der Begründung, die Unterhaltsabrede im Vertrag vom 17. August 2002 sei gültig, da die Mieterin den Beweis dafür nicht erbracht habe, dass sich die Vereinbarung insgesamt zu ihrem Nachteil ausgewirkt habe. Die Gegenforderung wegen angeblicher Mängel von insgesamt Fr. 222'269.-- hielt das Zivilgericht im Umfang von Fr. 150.80 für begründet. Es kam zum Schluss, die Mieterin habe Zahlungen an Werbemassnahmen nicht rechtsgrundlos geleistet, und verwarf die Behauptung, die Heiz- und Nebenkostenabrede sei insgesamt mangels Klarheit ungültig, wobei immerhin einige Positionen als zu pauschal erachtet und eine Forderung für Nebenkosten in Höhe von Fr. 2'780.85 (für 2009/10) als ungültig qualifiziert wurden. B.b. Mit Entscheid vom 16. Oktober 2015 wies das Appellationsgericht des Kantons Basel-Stadt die Berufung der Mieterin ab. Das Appellationsgericht folgte im Wesentlichen den Erwägungen der ersten Instanz und kam zum Schluss, mit der Überbindung der Unterhaltskosten sei der Mieterin kein Nachteil erwachsen und die mit hinreichender Klarheit ausgeschiedenen Nebenkosten seien der Mieterin gültig belastet worden, wobei der vom Zivilgericht als gültig erachtete Nebenkosten-Betrag geschützt wurde. C. Mit Beschwerde in Zivilsachen beantragt die Mieterin dem Bundesgericht, das Urteil des Appellationsgerichts des Kantons Basel-Stadt vom 16. Oktober 2015 sei vollumfänglich aufzuheben und die Klage sei abzuweisen, eventualiter sei das angefochtene Urteil aufzuheben und das Verfahren zur Vervollständigung des Beweisverfahrens und zur erneuten Entscheidung an die Vorinstanz zurückzuweisen, subeventualiter sei das angefochtene Urteil aufzuheben und die Sache an die erste Instanz zur Neubeurteilung zurückzuweisen. In ihrer weitschweifigen Beschwerde rügt die Beschwerdeführerin im Wesentlichen, die Vorinstanz habe den Sachverhalt unvollständig bzw. offensichtlich falsch festgestellt sowie Art. 256 Abs. 2 OR und Art. 257a OR verletzt. Die Beschwerdegegnerin und die Vorinstanz beantragen in ihren Vernehmlassungen die Abweisung der Beschwerde. Die Beschwerdeführerin hat unaufgefordert eine Replik eingereicht. D. Mit Präsidialverfügung vom 16. Januar 2016 wurde das Gesuch der Beschwerdeführerin um Gewährung der aufschiebenden Wirkung abgewiesen.