Faits : A. A.a. A.A._, né en 1965 à V._ (Etats-Unis), de nationalité américaine, et B.A._, née en 1969 à W._ (Royaume-Uni), de nationalité américaine et britannique, ont contracté mariage en 2003 à X._ (Etats-Unis). Ils sont les parents de C._, née en 2004 à Genève. B.A._ est également la mère de deux enfants majeurs nés d'une précédente union. A.A._ s'est établi à Genève en 1997. B.A._ l'a rejoint durant l'été 2003, avec ses enfants. Les époux vivent séparés depuis le 29 juin 2005. A.b. Par jugement du 5 juin 2008, le Tribunal de première instance du canton de Genève (ci-après: Tribunal) a prononcé le divorce des époux A._. Il a notamment attribué à A.A._ l'autorité parentale et la garde sur C._ et réservé à la mère un droit de visite d'une semaine sur deux et de la moitié des vacances scolaires. La Cour de justice du canton de Genève (ci-après: Cour de justice) a partiellement annulé ce jugement par arrêt du 16 janvier 2009 et a notamment attribué à B.A._ l'autorité parentale et la garde sur C._, un droit de visite étant réservé au père. Elle a également condamné A.A._ à verser à B.A._, à titre de contribution à son entretien, la somme de 15'000 fr. par mois jusqu'en décembre 2013 puis de 10'000 fr. par mois jusqu'en décembre 2021. Par arrêt du 12 octobre 2009, le Tribunal de céans a confirmé cette décision s'agissant des aspects relatifs aux droits parentaux et à la contribution due à l'entretien de l'ex-épouse (5A_127/2009). A.c. Depuis 2006, B.A._ entretient une relation sentimentale avec D._, qui est domicilié à New York. Elle vit désormais avec ce dernier après l'avoir rejoint à New York à la fin du mois de juin 2012. A.d. Par ordonnance de mesures provisionnelles du 6 mars 2012, A.A._, informé du prochain départ de B.A._, s'est notamment vu attribuer la garde et l'autorité parentale sur C._. Cette dernière s'est installée chez son père le 9 mars 2012. A.e. Statuant par jugement du 14 mars 2014 sur la requête de A.A._ en modification du jugement de divorce du 5 juin 2008 tel que réformé par les instances de recours, le Tribunal a annulé en partie ledit jugement (ch. 1 du dispositif), et a notamment attribué à A.A._ l'autorité parentale et la garde sur C._ (ch. 2) et réservé à B.A._ un droit de visite sur cette dernière, lequel s'exercerait, sauf accord contraire des parties, à raison de dix jours tous les deux mois à Genève pendant les périodes scolaires, ainsi que pendant les 2/3 des vacances scolaires (ch. 3). Ce jugement, confirmé par arrêt de la Cour de justice du 24 février 2015, a été annulé par arrêt du Tribunal de céans du 14 mars 2016 (5A_781/2015) sur la seule question de l'autorité parentale sur l'enfant. La cause a en conséquence été renvoyée à l'autorité cantonale qui a maintenu l'exercice de l'autorité parentale conjointe au terme de sa décision sur renvoi. B. B.a. Par acte du 21 septembre 2016, A.A._ a formé une seconde action en modification du jugement de divorce, objet de la présente procédure. Il a conclu principalement à la suppression de toute contribution à l'entretien de B.A._ avec effet au jour du dépôt de la demande. B.b. Par jugement du 28 septembre 2017, le Tribunal a réformé l'arrêt du 16 janvier 2009 de la Cour de justice, en ce sens que A.A._ a été condamné à verser à B.A._, dès le prononcé du jugement, par mois et d'avance, à titre de contribution à l'entretien de cette dernière, la somme de 7'500 fr. jusqu'au mois de décembre 2021. B.c. Par acte du 2 novembre 2017, A.A._ a fait appel de ce jugement sollicitant son annulation et concluant principalement à la suppression de toute contribution à l'entretien de son ex-épouse. B.A._ a formé un appel joint tendant principalement à l'annulation du jugement entrepris et au déboutement de A.A._ des fins de son action en modification du jugement de divorce du 5 juin 2008 et de l'arrêt de la Cour de justice du 16 janvier 2009. B.d. Par arrêt du 19 septembre 2018, expédié le 22 octobre 2018, la Cour de justice a rejeté l'appel et l'appel joint et confirmé le jugement entrepris. C. Par acte du 21 novembre 2018, A.A._ interjette un recours en matière civile au Tribunal fédéral contre cette décision. Il conclut principalement à l'annulation et à la réforme de l'arrêt querellé en ce sens que la contribution due à l'entretien de son ex-épouse est supprimée avec effet au jour du début de la présente procédure, à savoir le 21 septembre 2016. Subsidiairement, il conclut au renvoi de la cause à l'autorité précédente pour nouvelle décision au sens des considérants. Invitées à se déterminer, la Cour de justice s'est référée aux considérants de son arrêt et l'intimée a conclu au rejet du recours. Les parties ont répliqué et dupliqué, respectivement les 31 janvier et 14 février 2019, persistant toutes deux dans leurs conclusions.