Faits :
A.
A.a.
A.a.a. Par jugement du 13 avril 2015, le Tribunal de grande instance de Montbéliard (France) a condamné A._ à payer à Banque B._ la somme de 619'378,47 euros, solidairement avec un autre débiteur, et 700 euros à titre de dépens.
A.a.b. La Banque B._ a mandaté un huissier de justice pour signifier le jugement précité à A._. Cet huissier s'est rendu à l'adresse figurant sur le jugement, à U._ (France), mais n'y a trouvé personne. Il s'est alors rendu à la dernière adresse connue du débiteur, à V._ (France), où il a pu remettre une copie du jugement à la personne s'y trouvant, qui a déclaré accepter de la recevoir, et dresser le procès-verbal de signification.
A.a.c. Le 3 octobre 2018, la Banque B._ a écrit à A._ à une adresse à W._ pour l'inviter à lui remettre une proposition de règlement de la somme due en vertu du jugement du 13 avril 2015. Elle lui a envoyé un rappel le 15 du même mois, en précisant qu'une poursuite était introduite mais pourrait être suspendue si une solution pouvait être trouvée rapidement.
A.b. Le 19 octobre 2018, sur réquisition de la Banque B._, l'Office des poursuites de W._ a adressé au poursuivi un commandement de payer la somme de 723'686 fr. 94, plus intérêt à 5% dès le 4 octobre 2018, mentionnant comme cause de la créance le jugement du 13 avril 2015. La notification a été effectuée par un agent le 7 décembre 2018.
Le poursuivi a fait opposition totale le 18 décembre 2018.
B.
B.a.
B.a.a. Le 8 avril 2019, la Banque B._ a déposé devant le Tribunal civil des Montagnes et du Val-de-Ruz (ci-après: tribunal) une requête de mainlevée définitive de l'opposition, précisant que celle-ci devait porter sur un montant de 722'765 fr. 23, avec intérêt à 4,9% l'an sur le montant de 720'213 fr. 28.
B.a.b. Le tribunal a cité les parties par pli recommandé à une audience fixée au 3 juin 2019, pli que A._ a retiré le 30 avril 2019. Il n'a néanmoins pas comparu à l'audience.
B.a.c. Par décision du 20 juin 2019, le tribunal a prononcé la mainlevée définitive de l'opposition, à concurrence de 720'213 fr. 28, plus intérêt à 4,9% l'an dès le 4 octobre 2018, et de 2'551 fr. 95.
B.a.d. Cette décision a été envoyée par pli recommandé au poursuivi, le 20 juin 2019. Le pli a été avisé pour retrait le 24 juin 2019, avec un délai au 1 er juillet 2019. L'intéressé n'ayant pas retiré le recommandé à l'échéance du délai de garde de la Poste, le pli a été renvoyé au tribunal le 2 juillet 2019. Cette autorité a alors à nouveau envoyé la décision à A._, par courrier A, le 4 juillet 2019, sans commentaire ni lettre d'accompagnement.
B.b.
B.b.a. Par acte posté le 19 juillet 2019, A._ a recouru contre la décision de mainlevée définitive devant le Tribunal cantonal de la République et canton de Neuchâtel (ci-après : tribunal cantonal). Il a fait notamment valoir que le délai de recours avait commencé à courir à la date où il avait reçu le courrier A contenant la décision, qu'il était à l'étranger lorsque la décision lui a été notifiée sous pli recommandé, qu'il n'avait pas trouvé l'avis de retrait dans sa boîte aux lettres à son retour et qu'il n'était pas représenté par un mandataire professionnel au moment de la réception de la décision entreprise.
B.b.b. Par arrêt du 26 novembre 2019, le tribunal cantonal a déclaré irrecevable, pour cause de tardiveté, le recours interjeté par le poursuivi.
C.
Par acte posté le 13 janvier 2020, A._ interjette un recours en matière civile contre cet arrêt devant le Tribunal fédéral. Il conclut, principalement, à son annulation et à ce qu'il soit ordonné au tribunal cantonal d'entrer en matière sur son recours, et, subsidiairement, à son annulation et au renvoi de la cause à cette autorité pour nouvelle décision au sens des considérants. En substance, il se plaint d'arbitraire (art. 9 Cst.) dans la constatation des faits relatifs à la structure de la décision de première instance, de la violation du principe de la bonne foi (art. 9 Cst.) et de l'interdiction du formalisme excessif (art. 29 Cst.) en lien avec l'<ref-law>, et de la violation de l'<ref-law>.
Des observations n'ont pas été requises.
D.
Par ordonnance du 17 mars 2020, l'effet suspensif a été attribué au recours. La requête de mesures provisionnelles de l'intimée a par contre été rejetée, dans la mesure de sa recevabilité.

Considérant en droit :
1.
1.1. Le recours est dirigé en temps utile, compte tenu des féries judiciaires (art. 46 al. 1 let. c et 100 al. 1 LTF), contre une décision d'irrecevabilité. Il s'agit d'une décision finale, au sens de l'<ref-law>, dès lors qu'elle conduit à la clôture définitive de l'instance pour un motif tiré des règles de procédure (<ref-ruling> consid. 1.1). Sur le fond, elle a pour objet une décision de mainlevée définitive de l'opposition, soit une décision prise en matière civile (<ref-law>), et elle a été rendue par un tribunal supérieur statuant sur recours en dernière instance cantonale (<ref-law>). L'affaire est de nature pécuniaire et sa valeur litigieuse atteint 30'000 fr. (<ref-law>). Le recourant, qui a en outre pris part à la procédure devant l'autorité précédente, est particulièrement touché par la décision attaquée, qui a déclaré son appel irrecevable, et a un intérêt digne de protection à son annulation ou à sa modification (<ref-law>).
1.2. Des conclusions sur le fond du litige ne sont en principe pas admissibles contre une décision d'irrecevabilité. La raison en est que, sauf exceptions non réalisées en l'espèce (not. arrêt 5A_194/2012 du 8 mai 2012 consid. 5 in initioet les références), le Tribunal fédéral vérifie dans une telle situation uniquement si c'est à bon droit que l'instance précédente n'est pas entrée en matière sur le recours interjeté; il n'examine donc pas le fond de la contestation (<ref-ruling> consid. 1.3). En cas d'admission du recours, il ne réforme pas la décision attaquée mais l'annule et renvoie la cause à l'instance précédente pour qu'elle entre en matière sur le recours ou l'appel (arrêt 4A_330/2008 du 27 janvier 2010 consid. 2.1, non publié in <ref-ruling>, publié in JdT 2011 II p. 323).
1.3. Le recours en matière civile est donc, en principe, recevable.
2.
2.1. Le recours en matière civile peut être formé pour violation du droit, tel qu'il est délimité par les art. 95 et 96 LTF. Le Tribunal fédéral applique le droit d'office (<ref-law>). Cela étant, eu égard à l'exigence de motivation contenue à l'art. 42 al. 1 et 2 LTF, il n'examine en principe que les griefs soulevés; il n'est pas tenu de traiter, à l'instar d'une autorité de première instance, toutes les questions juridiques pouvant se poser, lorsque celles-ci ne sont plus discutées devant lui (<ref-ruling> consid. 2; <ref-ruling> consid. 1.4; <ref-ruling> consid. 1.1). Le recourant doit discuter les motifs de la décision entreprise et indiquer précisément en quoi il estime que l'autorité précédente a méconnu le droit (<ref-law>; <ref-ruling> consid. 2).
2.2. Le Tribunal fédéral statue sur la base des faits établis par l'autorité précédente (<ref-law>). Il ne peut s'en écarter que si ces faits ont été constatés de façon manifestement inexacte ou en violation du droit au sens de l'<ref-law> (<ref-law>), et si la correction du vice est susceptible d'influencer le sort de la cause (<ref-law>). Le recourant qui soutient que les faits ont été établis de manière manifestement inexacte (<ref-law>), à savoir que les constatations de fait sont arbitraires au sens de l'art. 9 Cst. (<ref-ruling> consid. 1.4.1), doit démontrer, par une argumentation précise, en quoi consiste la violation (<ref-law>).
3.
3.1. L'autorité cantonale a jugé que le recourant ne pouvait pas légitimement penser que la réception de la décision attaquée par courrier A, même si le délai de recours courait encore, en faisait partir un nouveau. Elle a retenu que la décision entreprise était datée du 20 juin 2019 et que le recourant l'avait reçue 20 jours plus tard, ce qui aurait dû attirer son attention. Par ailleurs, il était mentionné sur la dernière page de la décision que celle-ci avait été expédiée le 20 juin 2019 et qu'un exemplaire avait été envoyé au recourant par pli recommandé. En conséquence, le recourant ne pouvait pas ignorer que le tribunal avait déjà essayé de lui faire parvenir la décision et il devait faire preuve d'un minimum de prudence en prenant contact avec cette autorité afin de s'informer sur le délai de recours. L'autorité cantonale a ajouté que le recourant ne pouvait en tous les cas pas croire de bonne foi que le pli simple constituait la première ou la seule notification de la décision, qu'il devait avoir conscience que le délai de recours indiqué sur la décision courait déjà lorsqu'il avait reçu ce courrier et dès lors contacter le tribunal pour connaître le dies a quo du délai de recours. Sur la base de ces éléments, l'autorité cantonale a retenu que la notification de la décision entreprise avait eu lieu le 2 juillet 2019 et que le délai était arrivé à échéance le 11 juillet 2019, de sorte que, posté le 19 juillet 2019, le recours devait être déclaré irrecevable en raison de sa tardiveté.
3.2. Le recourant ne conteste pas avoir reçu l'avis de retrait relatif à l'envoi recommandé de la décision attaquée le 20 juin 2019. Il soutient en revanche que le second envoi de la décision par pli simple faisait courir un nouveau délai de 10 jours.
Premièrement, le recourant invoque la violation du principe de la bonne foi (art. 9 Cst.), de l'interdiction du formalisme excessif (art. 29 Cst.) ainsi que des règles relatives à la notification des décisions (<ref-law>). Il estime que la seconde notification par pli simple faisait partir un nouveau délai de recours et que l'autorité cantonale fait preuve de formalisme excessif en jugeant son recours irrecevable. Selon lui en effet, tout d'abord, cette seconde notification était intervenue avant l'échéance du délai de recours, le 9 juillet 2019. Ensuite, elle contenait une indication sans réserve des voies de droit. A cet égard, le recourant précise que la décision reçue par pli simple était un document original, avec les signatures originales du juge et de la greffière - sans signe qu'il s'agissait d'une seconde notification -, le timbre officiel du tribunal et l'indication sans réserve des voies de droit, dont le délai de 10 jours. Il ajoute que, s'il est mentionné au verso de la dernière page que la décision a été expédiée le 20 juin 2019 sous pli recommandé, cette communication n'indique pas qu'il s'agit d'une seconde notification ou que le délai de recours a commencé à courir antérieurement. Enfin, les conditions relatives à l'application du principe constitutionnel de la confiance étaient remplies. Il répète que la dernière page, qui mentionne la première expédition, constitue une page supplémentaire à la décision, soit le verso de la dernière page de celle-ci, ne contenant aucun autre texte que la mention " expédition le " suivi d'un timbre de date et d'une liste à puce; il ajoute que la pratique neuchâteloise est aussi, dans des situations de ce genre, d'apposer sur la dernière page un timbre de couleur rouge portant la mention " communication importante au verso " sur la dernière page de l'acte. Il soutient que la disposition du jugement est ainsi telle qu'un justiciable non rompu à la pratique judiciaire ne peut pas soupçonner que les informations contenues sur la dernière page puissent avoir une valeur contraignante, de sorte que la seule mention de la date de l'expédition en recommandé sur cette page ne suffit pas à renverser la présomption de bonne foi du justiciable lorsqu'il reçoit une seconde notification du jugement sans lettre d'accompagnement. A cet argument principal, le recourant ajoute qu'il n'était pas représenté, qu'aucune lettre d'accompagnement n'était annexée au second envoi, et qu'il est courant que la date de la décision ne corresponde pas à la date de son envoi.
Deuxièmement, le recourant invoque la violation de l'<ref-law>. Il soutient que son recours posté le 19 juillet 2019 est intervenu en temps utile compte tenu du fait que le second envoi par pli simple lui est parvenu le 9 juillet 2019.
Troisièmement, à supposer que la structure de la décision constitue un fait, le recourant invoque la violation de l'art. 9 Cst. en reprochant à l'autorité cantonale d'avoir omis de prendre en compte cet élément, notamment les signatures originales et l'absence de timbre mentionnant la communication importante au verso de la dernière page.
4.
La question qui se pose est de savoir si l'autorité cantonale a fait preuve de formalisme excessif en jugeant irrecevable le recours déposé le 19 juillet 2019 au motif que le second envoi par pli simple de la décision ne faisait pas courir un nouveau délai de recours de 10 jours.
4.1.
4.1.1. Le formalisme excessif est un aspect particulier du déni de justice prohibé par l'art. 29 al. 1 Cst.; il est réalisé lorsque la stricte application des règles de la procédure n'est commandée par aucun intérêt digne de protection, devient une fin en soi et entrave ou complique de manière insoutenable la réalisation du droit matériel (parmi plusieurs: arrêt 4A_635/2016 du 22 janvier 2018, non publié in <ref-ruling>; <ref-ruling> consid. 5.4.1 et les références).
4.1.2. Selon l'<ref-law>, les décisions sont notifiées par envoi recommandé ou d'une autre manière contre accusé de réception. L'alinéa 3 let. a de cette norme dit ensuite que l'acte est réputé notifié en cas d'envoi recommandé, lorsque celui-ci n'a pas été retiré, à l'expiration d'un délai de sept jours à compter de l'échec de la remise, si le destinataire devait s'attendre à recevoir la notification. En raison de la fiction de la notification, le destinataire est considéré comme s'il avait reçu l'envoi le dernier jour du délai (<ref-ruling> consid. 3.1).
De jurisprudence constante, un nouvel envoi de la décision et le retrait ultérieur du pli ne modifient en principe pas la fiction de notification (cf. not. <ref-ruling> consid. 4b/aa).
4.1.3. Dans un arrêt non publié, le Tribunal fédéral a toutefois admis qu'il faut réserver la protection du principe de la confiance (art. 5 al. 3 et 9 Cst., 52 CPC; arrêt 4A_53/2019 du 14 mai 2019 consid. 4.4.1, publié in Pra 2019 (108) p. 1098 n° 109 et in RSPC 2019 p. 338 n° 2249). Il en résulte que le délai peut se trouver prolongé lorsque, avant la fin du délai, le tribunal communique au plaideur une indication fondant sa confiance ou, par son comportement (contradictoire) éveille cette confiance. Une telle indication peut, entre autres, consister à notifier la décision à nouveau au plaideur, avant la fin du délai, avec une indication sans réserve des voies de droit. La protection de la confiance n'est cependant pas un automatisme. Pour l'admettre, il faut que la personne qui l'invoque ait pu légitimement se fier à l'indication du tribunal et que, sur cette base, elle ait pris des dispositions désavantageuses pour elle, sur lesquelles elle ne peut plus revenir. Dès lors, pour éviter toute confusion sur le point de départ du délai de recours, si le tribunal veut opérer une seconde tentative de notification, après que la décision est déjà réputée régulièrement notifiée en raison de la fiction de notification selon l'<ref-law>, il suffit de joindre à l'acte une lettre d'accompagnement qui éclaire la situation et exclut d'emblée tout éventuel malentendu concernant le cours du délai. Le tribunal peut par exemple ajouter l'indication selon laquelle il s'agit d'une seconde notification, qui ne change rien à la fiction de notification et au début du cours du délai (arrêt 4A_53/2019 précité consid. 4.4).
Au terme de son analyse, le Tribunal fédéral a toutefois laissé ouverte la question de savoir si l'envoi postal normal (<ref-law>) pouvait faire naître une confiance au sens précité (arrêt 4A_53/2019 précité consid. 5.2). La question mérite d'être soulevée. Certes, la jurisprudence rendue en procédure administrative n'exclut pas que la confiance du justiciable puisse être protégée alors même que la tentative de communication qui a, en fin de compte, porté ait eu lieu par pli simple (<ref-ruling> consid. 4). Néanmoins, en procédure civile, l'<ref-law> prévoit expressément que la notification des décisions doit se faire par envoi recommandé ou d'une autre manière contre accusé de réception, par opposition aux autres actes qui peuvent être notifiés par envoi postal normal (cf. <ref-law>). Une simple lecture de la loi permet donc de comprendre que seule est pertinente pour déterminer le point de départ du délai de recours la notification dans la forme spéciale de l'<ref-law>, ce qui devrait donc exclure toute confusion avec une notification postérieure sous pli simple, quel que soit le moment où celle-ci survient. Cela étant, la question n'a toujours pas à être tranchée au vu des circonstances du cas d'espèce.
4.2. En l'espèce, la notification de la décision de première instance par pli simple a certes eu lieu sans lettre d'accompagnement et alors que le délai de recours de dix jours courait encore, compte tenu de la fiction de la notification de la décision par envoi recommandé. Toutefois, comme l'a correctement relevé l'autorité cantonale, il était mentionné au verso de la dernière page de la décision que celle-ci avait déjà été expédiée le 20 juin 2019 sous pli recommandé au recourant. Il ne pouvait donc pas échapper à ce dernier qu'une première notification avait eu lieu par envoi recommandé et qu'elle avait une portée juridique vu que le tribunal en faisait état dans son jugement, malgré un second envoi sous pli simple. En cas de doute, il appartenait donc au recourant de prendre contact avec cette autorité pour savoir si le délai de recours courait depuis la première notification, en lien avec laquelle il faut rappeler que le recourant doit se laisser opposer fictivement en avoir connaissance, ou depuis la seconde qu'il admet avoir concrètement reçue. Il aurait pu de la sorte comprendre que le second envoi ne servait qu'à l'informer encore une fois qu'une décision lui avait été notifiée et que le délai de recours pour l'attaquer courait.
Les arguments du recourant ne suffisent pas à convaincre du contraire: on peut attendre du justiciable qu'il prenne connaissance de l'entier de la décision qui lui est communiquée et qu'il attache une attention particulière à la date de la notification, cette information étant décisive pour connaître le délai dans lequel il doit agir pour l'attaquer. Contrairement à ce que soutient le recourant, le justiciable ne peut pas partir de l'idée que certaines informations n'ont pas de valeur contraignante sous prétexte qu'elles se situent sur la dernière page de la décision. Il ne peut pas non plus être suivi lorsqu'il soutient qu'il n'y avait aucun signe de la part du tribunal que l'envoi par pli simple constituait une seconde notification, étant donné qu'était précisément indiqué un envoi précédent sous pli recommandé le 20 juin 2019. Enfin, le fait qu'il ne soit pas représenté ne lui est d'aucun secours, étant donné que l'information décisive permettant d'attendre raisonnablement de lui qu'il réagisse porte sur le fait, dont la compréhension ne suppose aucune connaissance juridique, qu'une première notification sous pli recommandé avait eu lieu avant celle par pli simple.
Au vu de ce qui précède, l'autorité cantonale n'a fait preuve d'aucun formalisme excessif en déclarant irrecevable le recours du recourant selon les art. 138 et 321 CPC. Les griefs du recourant doivent donc être rejetés.
4.3. Le grief d'arbitraire dans l'établissement des faits est sans objet, étant donné que la structure de la décision a été correctement prise en compte par l'autorité cantonale.
5.
En définitive, le recours doit être rejeté, dans la mesure où il est recevable. Les frais judiciaires, arrêtés à 7'000 fr., sont mis à la charge du recourant qui succombe (<ref-law>). Des dépens ne sont pas dus, l'intimée n'ayant pas été invitée à répondre au fond et ayant succombé dans ses conclusions sur mesures provisionnelles (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est rejeté dans la mesure où il est recevable.
2.
Les frais judiciaires, arrêtés à 7'000 fr., sont mis à la charge du recourant.
3.
Le présent arrêt est communiqué aux parties et au Tribunal cantonal du canton de Neuchâtel, Cour civile, Autorité de recours en matière civile.
Lausanne, le 16 avril 2020
Au nom de la IIe Cour de droit civil
du Tribunal fédéral suisse
Le Président : Herrmann
La Greffière : Achtari