Faits : A. A.a. Sur réquisition de D._ SA (par la suite B._ AG), l'Office des poursuites du district d'Aigle a établi, le 23 février 2015, dans la poursuite n° eee, un commandement de payer la somme de xxx fr. destiné à A._, mentionnant sous la rubrique titre de la créance ou cause de l'obligation: " Reprise de 9 ADB après faillite n° fff de Office des faillites de l'arrondissement de l'Est vaudois, Vevey (anciennement Office des faillites, Aigle), datés du 25.05.2000 de Fr. xxx, Fr. xxx, Fr. xxx, Fr. xxx, Fr. xxx, Fr. xxx, Fr. xxx, Fr. xxx et Fr. xxx ". Ce commandement de payer a été notifié le 2 mars 2015 à G._, au bénéfice d'une procuration. Il porte la signature du fonctionnaire qui a procédé à la notification ainsi que celle de G._ et la mention " opposition totale ". A.b. Par courrier adressé à l'Office des poursuites du district d'Aigle le 13 mai 2015, G._ a indiqué qu'elle avait retiré le commandement de payer n° eee le 2 mars 2015 à l'office postal d'Aigle, que le préposé du guichet lui avait déclaré qu'il " remplissait avant lui-même, l'opposition totale ou partielle " et qu'elle pourrait " après, lire de quoi il s'agissait ", qu'elle avait demandé d'inscrire les cinq mots " pas revenu à meilleure fortune " mais qu'elle s'était vu répondre qu'elle ne pouvait rien inscrire sur le document et devait seulement apposer sa signature, consigne qu'elle avait respectée de bonne foi. A.c. Par décision du 15 mai 2015, l'Office des poursuites du district d'Aigle a considéré que l'opposition " pas revenu à meilleure fortune " formulée dans la correspondance précitée était tardive et l'a en conséquence rejetée. B. B.a. Par acte du 22 mai 2015, le poursuivi a déposé une plainte LP contre la décision du 15 mai 2015, concluant, notamment, à ce qu'il soit constaté que l'exception de non-retour à meilleure fortune est valable, et à ce qu'ordre soit donné à l'Office des poursuites du district d'Aigle de consigner dite exception de non-retour à meilleure fortune et de transmettre le commandement de payer, poursuite ordinaire n° eee à la Justice de paix du district d'Aigle pour statuer sur l'exception de non-retour à meilleure fortune conformément à l'art. 265a al. 1 LP. Il a notamment fait valoir que G._, agissant au bénéfice d'une procuration, avait, le jour de la notification du commandement de payer litigieux, immédiatement déclaré à l'agent postal qu'elle souhaitait faire opposition et demandé que les mots " pas revenu à meilleure fortune " soient inscrits sur le commandement de payer, que l'employé postal avait toutefois refusé de le faire, que l'exception de non-retour à meilleure fortune n'en avait pas moins été valablement soulevée et qu'il n'avait constaté que cette exception n'avait pas été retenue par l'Office des poursuites qu'à l'occasion d'une audience de mainlevée qui s'était tenue devant le Juge de paix du district d'Aigle le 12 mai 2015. B.b. Par acte du 12 juin 2015, l'Office des poursuites du district d'Aigle a déclaré s'en remettre à justice. Il a par ailleurs produit un courrier qui lui avait été adressé par l'office postal d'Aigle le 19 mai 2015, dont il ressort en substance que le commandement de payer litigieux avait été notifié par H._, collaboratrice de la poste d'Aigle, que cette dernière avait elle-même inscrit les termes " opposition totale " à la demande de G._, que les termes " pas revenu à meilleure fortune " ne lui évoquaient rien et que si une telle demande avait été formulée, elle l'aurait indiqué après les termes " opposition totale ". Le courrier précise encore que l'office [postal] a un processus clairement établi pour la distribution des actes de poursuite, que chaque collaborateur le connaît et sait qu'il doit prendre note de ce " genre d'opposition spéciale ". B.c. Le Président du Tribunal de l'arrondissement de l'Est vaudois, en sa qualité d'autorité inférieure de surveillance, a tenu audience le 25 juin 2015. Entendue en qualité de témoin, G._ a déclaré ce qui suit: " Je suis une amie de M. A._. Je suis au bénéfice d'une procuration me permettant de retirer tout le courrier de ce dernier, avec signature. Le 2 mars 2015, j'ai été retir[er] à la Poste d'Aigle un commandement de payer. C'est le seul que j'ai retiré dans cette période-là. A cette occasion, je me suis présentée au guichet de la Poste avec la feuille que j'ai transmis[e] avec la procuration, comme je le fais d'habitude. En général, lorsque je retire le commandement de payer, on me le présente, ce qui n'a pas été le cas ce jour-là. Cela m'a étonné[e] donc j'ai demandé pourquoi l'homme du guichet ne me l'avait pas montré. Je vous confirme que c'était un monsieur, âgé d'environ 45 à 50 ans, châtain clair avec des lunettes. Comme il ne m'a pas présenté le commandement [de payer], j'ai donc fait opposition totale. J'ai demandé à écrire sur le document « pas revenu à meilleure fortune » mais l'homme au guichet m'a dit que je n'avais le droit que d'apposer ma signature. Ce que j'ai fait et je suis partie. Par la suite, je n'ai rien fait car ma mission était d'aller retirer le courrier, sans être chargée de gérer les affaires de M. A._. J'ai averti ce dernier de ce qui s'était passé à la Poste et il m'a dit de mettre le document dans sa boîte aux lettres, ce que j'ai fait. Je n'ai rien fait de plus par la suite. Je confirme que le 13 mai 2015 j'ai écrit à l'Office des poursuites pour expliquer ce qui [s]'est passé car c'était les indications de M. A._. Je vous confirme encore une fois que c'est bien un homme qui m'a notifié le commandement de payer. Lorsque j'ai signé le document, l'employé ne l'avait pas encore signé mais je ne peux pas vous le certifier. A la question de M. I._, je vous réponds que je connais un peu la situation financière de M. A._ et les soucis qu'il avait eus. Il m'a toujours dit de m'opposer lorsque je devais chercher un commandement de payer. Et sur les commandements de payer de D._ SA, je devais y inscrire « pas revenu à meilleure fortune ». " Entendue en qualité de témoin, H._ a déclaré ce qui suit: " Je vous présente l'autorisation de témoigner fournie par la Poste. Je ne me souviens plus précisément du commandement de payer du 2 mars 2015. Je vous confirme que c'est ma signature sur ce document. J'ai reconnu Mme G._ qui vient de sortir de la [salle] d'audience. Il est possible que je lui ai[e] notifié des commandements de payer autre que celui du 2 mars 2015. J'ai un collègue qui est âgé de plus de 50 ans, qui porte des lunettes et qui a des cheveux châtain. Il n'est pas possible que celui qui notifie le commandement de payer ne le signe pas. L'employé s'occupe du commandement de payer du début à la fin. A chaque client, je vais chercher le commandement de payer, je montre le tout au client pour qu'il en prenne connaissance et qu'il me dise ce qu'il veut faire. Je vous confirme que c'est ma signature, que j'ai écrit la date ainsi que la mention « opposition totale ». Je ne connais pas les termes « pas revenu à meilleure fortune », j'en ai pris connaissance uniquement lorsque la Poste a reçu le courrier de Mme G._. Cette dernière ne m'a ainsi jamais dit ces mots. " B.d. Par prononcé du 9 décembre 2015, le Président du Tribunal d'arrondissement de l'Est vaudois a admis la plainte présentée le 22 mai 2015 par A._ (I), dit que l'exception de non-retour à meilleure fortune formulée le 2 mars 2015 au commandement de payer, poursuite n° eee est valable (II), ordonné à l'Office des poursuites du district d'Aigle de consigner l'exception de non-retour à meilleure fortune formulée dans le cadre de la poursuite n° eee (III), ordonné à l'Office des poursuites du district d'Aigle de transmettre le commandement de payer, poursuite n° eee, à la Justice de paix du district d'Aigle pour statuer sur l'exception de non-retour à meilleure fortune conformément à l'art. 265a al. 1 LP (IV) et rendu la décision sans frais (V). B.e. Par arrêt du 10 mars 2016, notifié le 27 avril 2016, la Cour des poursuites et faillites du Tribunal cantonal vaudois a admis le recours interjeté par B._ AG contre le prononcé du 9 décembre 2015 et l'a réformé en ce sens que la plainte déposée par A._ le 22 mai 2015 est rejetée dans la mesure de sa recevabilité. C. Par acte posté le 9 mai 2016, A._ exerce un recours en matière civile au Tribunal fédéral contre l'arrêt du 10 mars 2016. Il conclut à sa réforme dans le sens des conclusions prises dans sa plainte du 22 mai 2015. Subsidiairement, il sollicite le renvoi de la cause à l'autorité précédente pour nouvelle décision dans le sens des considérants. Invitée à se déterminer sur la requête d'effet suspensif assortissant le recours, l'intimée a conclu à son rejet. La cour cantonale s'en est, quant à elle, remise à justice. Des observations sur le fond n'ont pas été requises. D. Par ordonnance présidentielle du 27 mai 2016, la requête d'effet suspensif a été admise.