Faits : A. A.a. Par jugement du 16 mars 2016, le Tribunal de première instance du canton de Genève (ci-après: Tribunal) a, sur requête de B._ SA, déclaré A._ en état de faillite dès ce jour à 14h15. A.b. Par acte déposé le 24 mars 2016 devant la Cour de justice du canton de Genève (ci-après: Cour de justice), A._ a recouru contre ce jugement, concluant à son annulation et à sa réforme en ce sens que la requête de faillite est rejetée. A.c. Par ordonnance du 24 mars 2016, reçue le 6 avril 2016 par A._, la Cour de justice a imparti à ce dernier un délai au 8 avril 2016 pour produire la " quittance pour solde " de l'Office des poursuites attestant du paiement (intérêts, frais et frais du Tribunal compris) de la dette en poursuite n° xxxx ou une lettre de retrait de la requête de faillite par la créancière. A.d. Par décision du 29 mars 2016, la Cour de justice a " accordé la suspension de l'effet exécutoire attaché au jugement entrepris ". A.e. Par arrêt du 25 avril 2016, communiqué pour notification aux parties le 28 avril 2016, la Cour de justice a rejeté le recours formé par A._ contre le jugement du 16 mars 2016, au motif que ce dernier n'avait produit aucun document dans le délai imparti. B. B.a. Par requête en restitution de délai expédiée le 3 mai 2016 à la Cour de justice, A._ a conclu, préalablement, à la suspension de l'effet exécutoire de l'arrêt du 25 avril 2016 et du jugement du 16 mars 2016, principalement, à la restitution du délai imparti par ordonnance du 24 mars 2016, et, cela fait, à l'annulation de l'arrêt du 25 avril 2016 et du jugement du 16 mars 2016, subsidiairement, au renvoi de la cause au Tribunal et, plus subsidiairement, à la reprise de l'instance. B.b. Par arrêt du 10 mai 2016, communiqué pour notification aux parties le 19 mai 2016, la Cour de justice a rejeté la requête en restitution de délai formée le 3 mai 2016. Vu cette issue, la Cour de justice a indiqué dans les considérants de son arrêt que la requête en suspension de l'effet exécutoire de l'arrêt du 25 avril 2016 et du jugement du 16 mars 2016 était sans objet. C. Par acte posté le 30 mai 2016, A._ exerce un recours en matière civile au Tribunal fédéral contre les arrêts du 25 avril 2016 et du 10 mai 2016. Le recourant conclut à la réforme de l'arrêt du 10 mai 2016 en ce sens que la requête en restitution de délai du 3 mai 2016 est admise et que la suspension de l'effet exécutoire de l'arrêt du 25 avril 2016 et du jugement du 16 mars 2016 est ordonnée. Subsidiairement, il sollicite le renvoi de la cause à l'autorité précédente pour nouvelle décision au sens des considérants. Le recourant sollicite par ailleurs d'être mis au bénéfice de l'assistance judiciaire pour la procédure fédérale. 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'est, quant à elle, référée aux considérants de son arrêt. Des observations sur le fond n'ont pas été requises. D. Par ordonnance présidentielle du 16 juin 2016, la requête d'effet suspensif assortissant le recours a été admise en ce sens que le prononcé de la faillite reste en force mais qu'aucun acte d'exécution de la décision attaquée ne doit être entrepris, les éventuelles mesures conservatoires déjà prises par l'Office en vertu des art. 162 ss, 170, 174 al. 3 et 221 ss LP demeurant toutefois en vigueur.