Faits : A. A.A._ (1963) et B.A._ (1965) se sont mariés en mars 1996. Ils ont eu deux enfants, nés en 1996 et 1998. Les parties se sont séparées en 2000. Par jugement du 29 août 2001, le juge du Tribunal du district de Zurich a prononcé leur divorce et notamment condamné l'ex-époux à contribuer à l'entretien de son ex-épouse à raison de 6'000 fr. par mois du 1er mars 2001 à la fin février 2008, puis de 3'500 fr. par mois dès cette date et jusqu'à la fin février 2014. B. Par mémoire du 26 novembre 2003, l'ex-époux a ouvert action en modification du jugement de divorce devant le Juge du district de Sierre, sollicitant que la contribution d'entretien en faveur de son ex-épouse soit réduite à 1'500 fr. par mois du 1er juin 2003 à fin février 2008. L'instruction a été suspendue le 8 avril 2009, des pourparlers étant en cours. Le 29 décembre 2011, l'ex-épouse a exposé qu'elle s'était remariée le 2 septembre 2011. Elle a donné acte à son ex-époux que plus aucune contribution d'entretien ne lui était due à compter du 1er septembre 2011, les pensions dues pour la période du 29 septembre 2003 au 31 août 2011 restant à payer. Par mémoire du 14 juin 2013, l'ex-époux a conclu principalement à la suppression de toute contribution d'entretien dès le 1er décembre 2003, subsidiairement à ce que la contribution d'entretien soit fixée à 500 fr. à compter de l'introduction de l'action en modification du jugement de divorce jusqu'au mois d'avril 2006, puis supprimée dès le mois de mai 2006. Le 16 août 2013, le Juge du district de Sierre a partiellement admis la requête en modification du jugement de divorce, en ce sens que la contribution d'entretien de 6'000 fr. par mois est suspendue du 1er décembre 2003 au 31 décembre 2004, et reprend effet du 1er janvier 2005 au 28 février 2008, pour être réduite à 3'500 fr. par mois du 1er mars 2008 au 31 décembre 2009. Dès le 1er janvier 2010 et jusqu'au 31 août 2011, la contribution d'entretien a été fixée à 1'750 fr. par mois. Elle a été supprimée à compter du 1er septembre 2011. Par jugement du 25 mai 2015, la Cour civile II du Tribunal cantonal du canton du Valais a rejeté l'appel interjeté par l'ex-époux contre cette décision. C. Par mémoire du 26 juin 2015, l'ex-époux exerce un recours en matière civile au Tribunal fédéral. Il conclut à l'annulation de l'arrêt entrepris et à sa réforme, en ce sens que la contribution d'entretien en faveur de son ex-épouse est supprimée à compter du mois de décembre 2003. Subsidiairement, il requiert le renvoi de la cause à l'autorité cantonale pour nouvelle décision. Invitées à se déterminer, l'intimée a sollicité le rejet du recours et la cour cantonale s'est référée aux considérants de sa décision. D. Par ordonnance présidentielle du 29 juin 2015, la requête d'effet suspensif a été rejetée.