Sachverhalt: A. Die Erben des X.A._ waren Eigentümer eines Geschäftshauses in Zürich. Nutzniesserin am Nachlass und somit auch am Geschäftshaus war die Witwe des Verstorbenen. Mit am 1. Juni 2012 öffentlich beurkundetem Vertrag wurde die Liegenschaft für 62 Mio Fr. an eine Versicherungsgesellschaft veräussert. Da der Verkauf ohne hypothekarische Belastung erfolgen sollte, wurden die auf dem Grundstück lastenden Hypotheken gegen eine Vorfälligkeitsentschädigung von Fr. 2'415'083.-- vorzeitig aufgelöst. Per Verkaufszeitpunkt verzichtete die Witwe auf ihr Nutzniessungsrecht am Grundstück bzw. am Veräusserungsgewinn. B. Die Vorfälligkeitsentschädigung wurde gegenüber der Witwe im Ausmass von Fr. 517'400.-- bei deren Einkommenssteuer zum Abzug zugelassen; bei einem an sich steuerbaren Einkommen von Fr. 517'400.-- wurde sie für ein steuerbares Einkommen von Fr. 0.-- veranlagt. C. Am 23. Mai 2013 erhob die Kommission für Grundsteuern der Stadt Zürich von den Erben eine Grundstückgewinnsteuer von Fr. 10'054'854.--. Sie liess die entrichtete Vorfälligkeitsentschädigung bei der Ermittlung des Grundstückgewinns nicht zum Abzug zu. Die dagegen gerichtete Einsprache blieb ebenso erfolglos wie die nachfolgende Beschwerde an das Verwaltungsgericht des Kantons Zürich. D. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 22. Dezember 2015 beantragen die Erben des X.A._ vor Bundesgericht, das verwaltungsgerichtliche Urteil vom 4. November 2015 aufzuheben. Die Vorfälligkeitsentschädigung sei bei der Bemessung des Grundstückgewinns im Ausmass von Fr. 1'897'683.-- (Fr. 2'415'083.-- minus Fr. 517'400.--) gewinnmindernd zu berücksichtigen. E. Die Kommission für die Grundsteuern der Stadt Zürich, das Kantonale Steueramt Zürich und das Verwaltungsgericht des Kantons Zürich schliessen auf Abweisung der Beschwerde (soweit darauf einzutreten sei). Die Eidgenössische Steuerverwaltung hat auf eine Stellungnahme verzichtet.