Faits: A. Ressortissant du Kosovo né le 1er septembre 1974, A._ est entré en Suisse le 21 juillet 1997 et y a déposé une demande d'asile. Par décision du 8 décembre 1997, l'Office fédéral des réfugiés (actuellement: l'Office fédéral des migrations; ci-après: l'Office fédéral) a rejeté la requête de l'intéressé et prononcé son renvoi de Suisse. Le recours formé contre cette décision a été rejeté le 5 juin 2000 et un délai au 6 septembre 2000 a été imparti à l'intéressé pour quitter le territoire suisse. Le 26 mai 2000, A._ a épousé B._, ressortissante suisse née le 15 décembre 1952. Il a de ce fait été mis au bénéfice d'une autorisation de séjour. Aucun enfant n'est issu de cette union. Le 29 septembre 2003, A._ a déposé une demande de naturalisation facilitée. Lors de l'instruction, le requérant et son épouse ont contresigné, le 14 juin 2004, une déclaration écrite aux termes de laquelle ils confirmaient vivre en communauté conjugale effective et stable, résider à la même adresse et n'envisager ni séparation, ni divorce. Par décision du 31 août 2004, l'Office fédéral a accordé la naturalisation requise. Les époux A._et B._ ont introduit une requête commune de divorce le 26 septembre 2005 et la dissolution de leur mariage a été prononcée le 30 janvier 2006. Le 18 octobre 2006, l'office de l'état civil de Martigny a délivré à A._ un certificat de capacité matrimoniale afin de lui permettre de contracter un nouveau mariage à l'étranger avec une compatriote, née le 14 novembre 1986 et domiciliée au Kosovo. B. Le 2 novembre 2006, l'Office fédéral a informé l'intéressé de son intention d'ouvrir une procédure visant à l'annulation de sa naturalisation facilitée. Dans ses observations du 15 décembre 2006, A._ a indiqué qu'aucune séparation n'était envisagée lors de la signature de la déclaration sur la communauté conjugale le 14 juin 2004 et qu'il avait éprouvé des sentiments forts à l'égard de son ex-épouse. Celle-ci, interrogée le 26 mars 2007, a affirmé que la décision de se marier avait été prise d'un commun accord, mais que l'initiative en revenait quand même à son ex-époux. Elle a souligné qu'ils s'étaient mariés pour fonder une famille, qu'ils n'avaient jamais abordé le sujet d'une descendance commune et que leur différence d'âge n'avait eu aucune influence sur leur décision de divorcer. Les problèmes conjugaux, qu'elle attribuait à une incompatibilité d'humeur, étaient survenus à partir du début de l'année 2005 et son ex-mari avait quitté le domicile conjugal environ quatre mois plus tard. Par décision du 8 novembre 2007, l'Office fédéral a prononcé, avec l'assentiment des autorités cantonales compétentes, l'annulation de la naturalisation facilitée accordée à A._. C. Le 18 février 2009, le Tribunal administratif fédéral a rejeté le recours de A._ contre la décision précitée. Il a considéré en substance que l'examen des faits pertinents, ainsi que leur déroulement chronologique, amenaient à la conclusion que l'intéressé avait choisi d'épouser une ressortissante suisse dans le but principal d'éluder les dispositions en matière de séjour et d'établissement. Celui-ci n'avait par ailleurs pas rendu vraisemblable la survenance d'un événement extraordinaire susceptible d'expliquer une détérioration rapide du lien conjugal. D. Agissant par la voie du recours en matière de droit public, A._ demande au Tribunal fédéral de réformer l'arrêt du Tribunal administratif fédéral et de prononcer sa naturalisation. Subsidiairement, il conclut à l'annulation de l'arrêt attaqué et au renvoi de la cause au Tribunal administratif fédéral pour nouvelle décision dans le sens des considérants. Le Tribunal administratif fédéral ainsi que l'Office fédéral ont renoncé à se déterminer. Par ordonnance du 15 avril 2009, le président de la Ire Cour de droit public a admis la requête d'effet suspensif contenue dans le recours.