Faits :
A.
A.a. B._, née en 1989, et A._, né en 1976, tous deux de nationalité algérienne, se sont mariés à U._ (Algérie) le 2 juin 2013.
Le 4 octobre 2013, B._ est venue rejoindre son époux en Suisse où celui-ci est domicilié depuis 2006.
A.b. En mai 2014, alors qu'elle était enceinte, B._ a quitté le domicile conjugal, alléguant que son époux la séquestrait dans leur appartement et lui imposait des règles strictes, telles que l'interdiction de sortir seule ou le port du voile. Elle a déposé par la suite une plainte pénale pour séquestration et contrainte, accusations que A._ a contestées, déposant à son tour une plainte pénale contre son épouse pour calomnie, diffamation, dénonciation calomnieuse et induction de la justice en erreur. Le dossier ne contient pas d'autre élément quant à la suite de ces procédures.
Dans un premier temps, B._ a été hébergée chez sa famille et une connaissance, puis a logé dans un foyer d'urgence dès le 25 juillet 2014.
La fille commune des parties, C._, est née le 18 août 2014 à Genève.
B.
B.a. Le 12 août 2014, A._ a déposé une requête de divorce en Algérie tendant à la dissolution du lien conjugal.
B.b. Par acte du 4 septembre 2014, B._ a saisi le Tribunal de première instance du canton de Genève (ci-après: le Tribunal) d'une requête de mesures protectrices de l'union conjugale, sollicitant, notamment, l'autorisation de vivre séparée de son époux, l'attribution en sa faveur de la garde de l'enfant C._, en réservant un droit de visite à A._ selon les prescriptions du Service de protection des mineurs (ci-après: le SPMi) et la condamnation de A._ à lui verser, par mois et d'avance, un montant de 2'000 fr. à titre de contribution à l'entretien de la famille, soit 1'000 fr. pour l'entretien de sa fille et 1'000 fr. pour son propre entretien, dès le 1 er juin 2014.
B.c. Lors de l'audience du 18 novembre 2014 devant le Tribunal, A._ a soulevé une exception de litispendance, compte tenu de la procédure de divorce pendante en Algérie. Il a conclu à l'irrecevabilité de la requête de son épouse, alléguant que le Tribunal aurait dû être saisi d'une demande de mesures provisionnelles et non pas d'une requête de mesures protectrices.
B._ s'est opposée à l'incident, contestant la compétence des tribunaux algériens en raison du domicile des parties en Suisse.
B.d. Par jugement sur incident du 23 janvier 2015, le Tribunal a admis sa compétence pour connaître de la requête de mesures protectrices formée par B._, au motif que les tribunaux suisses pouvaient ordonner des mesures provisoires, respectivement des mesures protectrices de l'union conjugale, en vertu de l'<ref-law>, quand bien même une action en divorce était pendante uniquement devant un juge étranger, pour autant que les mesures requises soient urgentes et nécessaires, ce qui paraissait être le cas en l'occurrence.
C.
C.a. Le 28 janvier 2015, le Tribunal de U._ (Algérie) a prononcé le divorce des époux, se déclarant au préalable compétent en application de l'art. 12 du Code civil algérien, compte tenu de la nationalité algérienne des deux parties et du fait qu'elles avaient contracté mariage en Algérie. Il a, en outre, condamné A._ à verser à B._ la somme de 30'000 dinars (équivalent à 280 fr.) à titre de pension de retraite légale. En revanche, il ne s'est pas prononcé sur le sort du domicile conjugal ni sur le sort de l'enfant, n'ayant pas été saisi de ces questions.
C.b. Le 29 juin 2015, A._ a fait transcrire le jugement de divorce algérien du 28 janvier 2015 au Registre suisse de l'Etat civil.
C.c. Par courrier adressé le 21 octobre 2015 à la Direction cantonale de l'Etat civil, B._ a contesté la transcription du jugement de divorce algérien et requis la rectification du registre, déclarant avoir eu connaissance de dite transcription le jour même.
D.
D.a. Par jugement de mesures protectrices de l'union conjugale du 30 juin 2015, notifié aux parties avec sa motivation complète le 5 octobre 2015, le Tribunal a notamment autorisé les époux A._ et B._ à vivre séparés (ch. 1 du dispositif), attribué à B._ la garde sur l'enfant C._ (ch. 2), réservé à A._ un droit de visite s'exerçant, dans un premier temps au sein d'un Point Rencontre, à raison de deux heures par quinzaine (ch. 3), instauré une curatelle de surveillance et d'organisation du droit de visite au sens de l'<ref-law> (ch. 4), condamné A._ à verser en mains de B._, par mois et d'avance, allocations familiales éventuelles non comprises, le montant de 500 fr. à compter du 1 er juin 2014 au titre de contribution à l'entretien de sa famille (ch. 6) et attribué la jouissance du domicile conjugal, de même que les droits et obligations y relatifs, à B._ (ch. 7). Le Tribunal a prononcé ces mesures pour une durée indéterminée (ch. 10).
D.b. Le 15 octobre 2015, A._ a appelé de ce jugement par-devant la Cour de justice du canton de Genève (ci-après: Cour de justice) requérant l'annulation des seuls ch. 6 et 7 de son dispositif et leur réforme en ce sens qu'il est condamné à verser en mains de B._, allocations familiales non comprises, une contribution d'entretien mensuelle pour l'enfant de 150 fr. pour les mois de mars à juin 2015, qu'il est libéré de toute contribution à l'entretien de son épouse et qu'il est dit et constaté que l'attribution de la jouissance exclusive du domicile conjugal est devenue sans objet. Il a sollicité la confirmation du jugement querellé pour le surplus.
D.c. Par arrêt du 12 février 2016, la Cour de justice a confirmé le jugement entrepris.
E.
Par acte du 15 mars 2016, A._ interjette un recours en matière civile au Tribunal fédéral contre l'arrêt du 12 février 2016. Il conclut principalement à son annulation en tant qu'il a confirmé les chiffres 6 et 10 du dispositif du jugement de première instance et à sa réforme en ce sens qu'il est condamné à verser en mains de B._ la somme de 200 fr. par mois et d'avance, allocations familiales non comprises, au titre de l'entretien de C._ et ce du 1 er juin 2014 jusqu'au 28 janvier 2015; subsidiairement, il conclut à l'annulation de l'arrêt entrepris en tant qu'il a confirmé les chiffres 6 et 10 du dispositif du jugement de première instance et au renvoi de la cause à l'autorité cantonale pour nouvelle décision au sens des considérants. Il requiert également d'être mis au bénéfice de l'assistance judiciaire pour la procédure fédérale.
Invitées à se déterminer, la Cour de justice s'est référée aux considérants de son arrêt et l'intimée a conclu principalement à l'irrecevabilité du recours et, subsidiairement, à son rejet, sollicitant également d'être mise au bénéfice de l'assistance judiciaire. Le recourant a répliqué le 5 août 2016, persistant dans ses conclusions. L'intimée a renoncé à dupliquer par courrier du 10 août 2016.

Considérant en droit :
1.
Le présent recours a été déposé en temps utile (<ref-law>) ainsi que dans la forme légale (<ref-law>), par la partie qui a succombé dans ses conclusions prises devant l'autorité précédente (<ref-law>), contre une décision finale (<ref-law>) dans une contestation civile (<ref-law>) rendue sur recours par une autorité supérieure statuant en dernière instance cantonale (art. 75 al. 1 et 2 LTF). Nonobstant l'avis contraire de l'intimée, la valeur litigieuse atteint en l'espèce 30'000 fr. dès lors que la durée de l'obligation d'entretien dans le cadre de la procédure de mesures protectrices de l'union conjugale est incertaine (art. 51 al. 1 let. a et al. 4 et art. 74 al. 1 let. b LTF; arrêt 5A_336/2007 du 5 octobre 2007 consid. 1.2). Le présent recours en matière civile est en principe recevable au regard des dispositions qui précèdent.
2.
2.1. Dès lors que la décision attaquée porte sur des mesures protectrices de l'union conjugale, lesquelles sont considérées comme des mesures provisionnelles au sens de l'<ref-law> (<ref-ruling> consid. 5 p. 396 s.), seule peut être invoquée à leur encontre la violation de droits constitutionnels. Le Tribunal fédéral n'examine de tels griefs que s'ils ont été invoqués et motivés ("principe d'allégation", <ref-law>), à savoir expressément soulevés et exposés de manière claire et détaillée (<ref-ruling> consid. 2.2 p. 232; <ref-ruling> consid. 3.2 p. 88; <ref-ruling> consid. 5 p. 396 s.; <ref-ruling> consid. 1.4 p. 287). Le recourant qui se plaint de la violation d'un droit fondamental ne peut donc se borner à critiquer la décision attaquée comme il le ferait en instance d'appel, où l'autorité de recours jouit d'une libre cognition; il ne peut, en particulier, se contenter d'opposer sa thèse à celle de l'autorité cantonale, mais doit démontrer ses allégations par une argumentation précise (<ref-ruling> consid. 3 p. 351 s.; <ref-ruling> consid. 3.2 p. 399). Le Tribunal fédéral n'entre pas en matière sur les critiques de nature appellatoire (<ref-ruling> consid. 10.1 p. 445; <ref-ruling> consid. 2 p. 592).
2.2. Le Tribunal fédéral statue sur la base des faits établis par l'autorité précédente (<ref-law>). Dans l'hypothèse d'un recours soumis à l'<ref-law>, une rectification ou un complètement de l'état de fait n'entre en considération que si l'autorité précédente a violé des droits constitutionnels, les art. 95, 97 et 105 al. 2 LTF ne s'appliquant pas directement (<ref-ruling> consid. 7.1 p. 398 et 585 consid. 4.1 p. 588). Le Tribunal fédéral n'examine ce grief que s'il a été invoqué et motivé par le recourant conformément au principe d'allégation susmentionné (<ref-ruling> consid. 2.8 p. 494; <ref-ruling> consid. 2.2 p. 246; <ref-ruling> consid. 2.1 p. 31; <ref-ruling> consid. 1.3 p. 261 s.).
3.
Comme le relève à juste titre l'intimée dans sa réponse du 18 juillet 2016, les conclusions prises par le recourant dans son recours en matière civile du 15 mars 2016 divergent de celles qu'il avait formulées dans son appel du 15 octobre 2015, ce qui conduit en principe à l'irrecevabilité des conclusions nouvelles (<ref-law>). En effet, il apparaît que le recourant sollicitait, dans son écriture du 15 octobre 2015, l'annulation des seuls chiffres 6 et 7 du dispositif du jugement de première instance portant sur la contribution qu'il a été condamné à verser à l'entretien de sa famille ainsi que sur l'attribution de la jouissance du domicile conjugal à l'intimée, alors que dans son recours fédéral du 15 mars 2016, il requiert l'annulation des chiffres 6 et 10 dudit dispositif, le chiffre 10 précisant que les mesures protectrices ordonnées dans le jugement attaqué le sont pour une durée indéterminée. A l'examen de ses conclusions en réforme, on s'aperçoit toutefois que le recourant renonce ce faisant à contester l'attribution de la jouissance du domicile conjugal à l'intimée et accepte de verser un montant supérieur pour l'entretien de sa fille, à savoir la somme de 200 fr. par mois du 1er juin 2014 jusqu'au 28 janvier 2015 (montant total: 1'600 fr.) en lieu et place des 150 fr. par mois qu'il se déclarait prêt à verser précédemment pour les mois de mars à juin 2015 uniquement (montant total: 600 fr.). Dans la mesure où le recourant procède ainsi à une réduction de ses conclusions, procédé admissible au regard de l'<ref-law>, les conclusions nouvelles prises devant la Cour de céans sont recevables (<ref-ruling> consid. 3.4.2 p. 365; arrêts 5A_933/2014 du 16 avril 2015 consid. 3.3.1; 5A_8/2008 du 11 avril 2008 consid. 1.1).
Il y a également lieu de constater que, hormis la question de la contribution d'entretien, le recourant n'a pris aucune conclusion s'agissant des autres points tranchés par la cour cantonale, à savoir notamment l'attribution de la garde de l'enfant à l'intimée et la fixation d'un droit de visite en sa faveur, ce malgré le fait qu'il conteste la compétence de la cour cantonale pour rendre des mesures protectrices de l'union conjugale postérieurement au prononcé du jugement de divorce algérien. Un tel procédé ne saurait être compris que comme une requête implicite de confirmation des points dont le recourant ne sollicite pas l'annulation. L'admission d'une telle requête nécessite toutefois que, nonobstant le prononcé du jugement de divorce en Algérie, la Cour de justice fût encore compétente pour rendre des mesures protectrices de l'union conjugale au moment du prononcé litigieux, d'où la nécessité d'examiner cette question (cf. infra consid. 5 et 6).
4.
4.1. Le recourant reproche en premier lieu à la cour cantonale d'avoir considéré que l'intimée avait valablement contesté la transcription du jugement de divorce algérien au Registre suisse de l'Etat civil. Il relève à cet égard que l'intimée s'est contentée d'adresser un courrier à l'Etat civil de Genève pour faire part de son opposition à cette transcription au motif que le jugement de divorce n'avait pas encore été reconnu par les autorités suisses. Il soutient qu'un tel courrier n'est pas suffisant pour valoir contestation alors qu'une voie de recours était ouverte en vertu de l'art. 90 OEC contre la décision de transcription au sens de l'art. 23 OEC. En retenant le contraire, la cour cantonale avait procédé à une appréciation insoutenable des preuves et constaté les faits de manière arbitraire.
Le recourant reproche ensuite à la cour cantonale d'avoir à tort considéré que la question de la reconnaissance en Suisse du jugement de divorce algérien dans le cadre de la procédure de mesures protectrices de l'union conjugale pouvait rester ouverte.
Il fait également grief à la cour cantonale de l'avoir condamné à verser une contribution à l'entretien de sa famille et donc, implicitement, également à l'entretien de l'intimée. Selon lui, l'autorité cantonale n'était pas fondée à prendre des mesures protectrices de l'union conjugale dès lors que de telles mesures ne peuvent plus être prononcées pour la période postérieure au jugement de divorce. La motivation de l'autorité cantonale sur ce point serait d'autant plus arbitraire qu'elle est contradictoire puisque la Cour de justice a indiqué au considérant 4.3 de l'arrêt entrepris que l'intimée ne pouvait prétendre à une contribution d'entretien au vu des revenus réalisés par le recourant. La cour cantonale avait par conséquent appliqué arbitrairement les art. 163 et 176 al. 2 CC, ainsi que l'<ref-law>.
Compte tenu du prononcé de divorce algérien, il fait valoir que la cour cantonale n'était pas davantage fondée à rendre des mesures protectrices de l'union conjugale s'agissant de la contribution d'entretien en faveur de l'enfant des parties. Il estime de ce fait que la contribution due à sa fille aurait dû être limitée au 28 janvier 2015, date du prononcé de divorce en Algérie, et ne pouvait être ordonnée pour une durée indéterminée. En le condamnant, sur mesures protectrices de l'union conjugale, à verser une pension à sa fille au-delà du prononcé du jugement de divorce, il estime que la cour cantonale a appliqué arbitrairement l'<ref-law> ainsi que les art. 176 al. 3 et 276 ss CC.
4.2. La cour cantonale a, dans un premier temps, relevé que le juge suisse était compétent pour prononcer des mesures protectrices de l'union conjugale et le restait tant et aussi longtemps que le jugement de divorce étranger n'avait pas été reconnu en Suisse selon la procédure des <ref-law>. Elle a ensuite considéré qu'elle était en l'espèce compétente pour trancher les questions relatives au domicile conjugal et à la contribution d'entretien en faveur de l'enfant dans la mesure où le juge algérien n'avait pas été saisi de ces questions et que le jugement de divorce algérien n'avait par conséquent pas acquis autorité de chose jugée sur ces points. S'agissant en revanche de la contribution d'entretien due en faveur de l'épouse, le juge algérien avait statué sur cette question, de sorte qu'il fallait s'interroger sur la reconnaissance du jugement de divorce. A cet égard, elle a relevé que le recourant avait fait procéder à la transcription du jugement de divorce étranger au Registre suisse de l'Etat civil le 29 juin 2015, ce qui remplaçait toute procédure d' exequaturet permettait d'obtenir sa reconnaissance. Cela étant, en l'espèce, l'intimée s'était opposée à cette transcription dès qu'elle en avait eu connaissance, sollicitant son annulation avec effet rétroactif. La Cour de justice en a déduit qu'il lui appartenait donc de statuer, à titre préjudiciel, sur la reconnaissance en Suisse du jugement de divorce algérien du 28 janvier 2015. Elle a toutefois estimé que cette question pouvait en définitive rester ouverte puisque, quand bien même dit jugement pourrait être reconnu en Suisse, la contribution d'entretien mise à la charge du recourant couvrait tout juste les besoins de l'enfant. Or, dans la mesure où la question de l'entretien de l'enfant n'avait pas été examinée dans le jugement de divorce algérien, celui-ci ne déployait pas d'effets à cet égard, de sorte que la reconnaissance dudit jugement n'avait pas d'influence sur l'issue du litige. Elle a ensuite traité les griefs du recourant en lien avec le montant de la contribution d'entretien due à l'entretien de la famille et l'attribution à l'intimée de la jouissance du domicile conjugal et les a rejetés.
5.
5.1. Lorsqu'une partie se prévaut d'un jugement de divorce étranger dans le cadre d'une procédure de mesures protectrices de l'union conjugale introduite en Suisse où elle est domiciliée, le juge suisse demeure compétent (<ref-law>) pour rendre des mesures protectrices de l'union conjugale (<ref-law>) tant que le jugement invoqué n'a pas été reconnu en Suisse selon la procédure applicable (<ref-ruling> consid. 2b p. 237 s.; arrêt 5A_76/2007 du 30 mai 2007 consid. 3.1). Ce cas de figure doit être distingué de celui où une procédure de divorce introduite devant un tribunal étranger compétent est encore pendante. Dans cette dernière hypothèse, à moins que le juge des mesures protectrices constate d'emblée que le jugement de divorce étranger ne pourra manifestement pas être reconnu en Suisse, la compétence des autorités suisses pour rendre des mesures protectrices de l'union conjugale tombe, seules des mesures provisionnelles pouvant être ordonnées en application de l'<ref-law> durant la procédure de divorce pendante à l'étranger ou selon l'<ref-law> si une procédure de divorce est également pendante en Suisse (<ref-ruling> consid. 3.2 et 3.3 p. 328; arrêt 5A_588/2014 du 12 novembre 2014 consid. 4.4).
5.2. A teneur de l'<ref-law>, un jugement de divorce étranger est reconnu en Suisse lorsqu'il a été rendu dans l'Etat du domicile ou de la résidence habituelle, ou dans l'Etat national de l'un des époux, ou s'il est reconnu dans l'un de ces Etats. Cette disposition doit être lue en relation avec les normes générales posées aux <ref-law>, qui prévoient en substance qu'une décision étrangère est reconnue en Suisse pour autant que les autorités judiciaires de l'Etat dont émane la décision étaient compétentes, que celle-ci n'est plus susceptible d'un recours ordinaire et qu'elle n'est pas manifestement incompatible avec l'ordre public suisse (<ref-ruling> consid. 2a p. 330).
En matière d'état civil, c'est la transcription du jugement de divorce étranger dans les registres d'état civil qui constitue la reconnaissance d'une telle décision (BUCHER, in Commentaire romand, Loi sur le droit international privé, 2011, n° 1 ad <ref-law>; BERTI/DÄPPEN, in Basler Kommentar, Internationales Privatrecht, 3 e éd., 2013, n° 2 ad <ref-law>; BUCHER/BONOMI, Droit international privé, 3 e éd., 2013, n os 306 et 583 s.; cf. aussi: arrêt 5A.6/1996 du 19 avril 1996 consid. 2b). Il s'ensuit qu'une déclaration formelle d' exequatur n'est pas nécessaire (arrêt 5A_697/2007 du 3 juillet 2008 consid. 2.2). Cette procédure est régie par l'<ref-law>, certaines modalités étant par ailleurs réglées par l'art. 23 de l'Ordonnance sur l'état civil du 28 avril 2004 (OEC; RS 211.112.2).
L'autorité cantonale de surveillance dispose d'un plein pouvoir d'examen dans l'application de l'art. 23 OEC concernant la transcription d'actes étrangers, notamment d'un jugement de divorce, qui peut même porter sur de délicates questions de droit international privé. En outre, la compétence de l'autorité cantonale de surveillance est considérée comme exclusive, dans la mesure où elle exclut une procédure cantonale d' exequatur. L'<ref-law> est fondé sur les mêmes principes. Cela ne signifie toutefois nullement que la décision de l'autorité cantonale de surveillance qui ordonne l'inscription fasse obstacle à une action d'état tendant à obtenir la radiation ou la modification de l'inscription en question. Une telle décision n'est en effet que la condition de l'inscription dans les registres de l'état civil mais n'apporte pas la preuve irréfragable des faits qu'elle constate et dont l'<ref-law> permet expressément de prouver l'inexactitude. La décision administrative d'inscription ne préjuge donc en rien de la compétence du juge pour statuer sur la validité du fait constaté par l'inscription. Elle a uniquement une valeur déclarative et n'acquiert pas la force de chose jugée au sens matériel (<ref-ruling> consid. 4 p. 12 s. et les références relatif à l'art. 137 aOEC). Par conséquent, quand bien même le changement d'état obtenu à l'étranger a déjà été transcrit dans le Registre suisse de l'Etat civil, le juge du divorce n'est pas lié par cette décision (OTHENIN-GIRARD, La transcription des décisions et des actes étrangers à l'état civil, in Revue de l'état civil (REC) 1998, p. 163 ss, 166). Il peut, cas échéant, faire rectifier l'inscription en application de l'<ref-law> (<ref-ruling> consid. 4b p. 260 et les arrêts cités; arrêt 5A_756/2015 du 16 juin 2016 consid. 3).
6.
En l'espèce, amenée à statuer dans une procédure de mesures protectrices de l'union conjugale dans le cadre de laquelle un jugement de divorce étranger d'ores et déjà transcrit au Registre suisse de l'Etat civil était invoqué, la cour cantonale ne pouvait s'abstenir de se prononcer sur la question de la reconnaissance dudit jugement. En effet, il ressort de la jurisprudence susmentionnée que, dès lors qu'un jugement de divorce avait été rendu à l'égard des parties en Algérie et transcrit au Registre suisse de l'Etat civil, la cour cantonale demeurait compétente pour rendre des mesures protectrices de l'union conjugale, y compris sur les questions non traitées dans le jugement de divorce étranger, uniquement dans l'hypothèse où celui-ci n'était pas reconnu faute de remplir les conditions des art. 65 al. 1 et 25 ss LDIP. En revanche, si le jugement étranger devait être reconnu en application de ces dispositions, seule une procédure en complément ou en modification du jugement de divorce étranger au sens de l'<ref-law> était encore possible, dans le cadre de laquelle des mesures provisionnelles pouvaient être prises en application de l'<ref-law> (arrêt 5A_475/2015 du 17 décembre 2015 consid. 1.4 et la référence). Pour les mêmes motifs, la critique de l'intimée selon laquelle le recourant ne peut plus contester la compétence des autorités suisses pour connaître de sa requête de mesures protectrices de l'union conjugale dès lors que celle-ci a été admise par un jugement du 23 janvier 2015 non contesté par le recourant est infondée. En effet, dans la mesure où le jugement de divorce algérien a été rendu postérieurement au 23 janvier 2015, celui-ci peut, au regard de la jurisprudence sus-évoquée, avoir eu une incidence sur la compétence des autorités suisses pour rendre des mesures protectrices de l'union conjugale. Il s'ensuit que la question d'une éventuelle reconnaissance du jugement de divorce algérien devait impérativement être tranchée dans le cas d'espèce, ne serait-ce que pour déterminer si le juge saisi, à savoir le juge des mesures protectrices de l'union conjugale, était encore compétent pour rendre de telles mesures.
En outre, quand bien même le jugement de divorce étranger a en l'espèce déjà été transcrit au Registre suisse de l'Etat civil et que cette transcription suffit à valoir reconnaissance d'une telle décision, le juge saisi demeure compétent pour statuer sur la validité du fait constaté par l'inscription et, cas échéant, faire rectifier cette dernière. La question de la validité de la contestation de la transcription effectuée par l'intimée n'est à cet égard pas déterminante. Le fait que le jugement de divorce algérien ait déjà été transcrit ne fait par conséquent pas obstacle à un refus de reconnaissance si le juge saisi estime que les conditions des art. 65 al. 1 et 25 ss LDIP ne sont pas remplies.
7.
Sur le vu de ce qui précède, le recours se révèle bien fondé et doit par conséquent être admis, ce qui en scelle le sort sans qu'il y ait lieu d'examiner à ce stade les critiques du recourant portant sur la contribution à l'entretien de sa famille qu'il a été condamné à verser. L'arrêt querellé sera ainsi annulé et la cause renvoyée à la Cour de justice afin que la question de la reconnaissance du jugement de divorce algérien du 28 janvier 2015 soit tranchée à titre préjudiciel. Il conviendra, dans un deuxième temps, de rendre les mesures protectrices de l'union conjugale qui s'imposent dans l'hypothèse où le jugement de divorce ne serait pas reconnu, ou, en cas de reconnaissance de celui-ci, de le compléter s'agissant des questions qui n'y ont pas été traitées ou sur lesquelles la reconnaissance a été refusée. Les frais judiciaires sont mis à la charge de l'intimée, qui succombe (<ref-law>), et qui versera en outre des dépens au recourant (68 al. 1 et 2 LTF). La requête d'assistance judiciaire du recourant est admise. La demande d'assistance judiciaire de l'intimée est admise (<ref-law>). Les frais judiciaires lui incombant seront donc provisoirement supportés par la Caisse du Tribunal fédéral (<ref-law>). Si l'octroi de l'assistance judiciaire ne dispense pas l'intimée du paiement de dépens, ceux-ci seront toutefois, au vu de sa situation financière et du fait qu'il est d'emblée vraisemblable qu'ils ne pourront être recouvrés, supportés provisoirement par la Caisse du Tribunal fédéral, étant rappelé que l'intimée est tenue de rembourser ultérieurement la Caisse si elle est en mesure de le faire (<ref-law>; arrêt 5A_558/2014 du 7 septembre 2015 consid. 7.2).

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est admis, l'arrêt attaqué est annulé et la cause est renvoyée à l'autorité cantonale pour instruction complémentaire et nouvelle décision dans le sens des considérants.
2.
La requête d'assistance judiciaire du recourant est admise et Me Vincent Solari, avocat à Genève, lui est désigné comme conseil d'office pour la procédure fédérale.
3.
La requête d'assistance judiciaire de l'intimée est admise et Me Camille Maulini, avocate à Genève, lui est désignée comme conseil d'office pour la procédure fédérale.
4.
Les frais judiciaires, arrêtés à 1'500 fr., sont mis à la charge de l'intimée. Ils sont provisoirement supportés par la Caisse du Tribunal fédéral.
5.
L'intimée versera au recourant une indemnité de 2'000 fr. à titre de dépens, laquelle sera provisoirement supportée par la Caisse du Tribunal fédéral.
6.
Une indemnité de 2'000 fr., supportée par la Caisse du Tribunal fédéral, est allouée à Me Camille Maulini à titre d'honoraires d'avocat d'office.
7.
Le présent arrêt est communiqué aux parties et à la Chambre civile de la Cour de justice du canton de Genève.
Lausanne, le 26 août 2016
Au nom de la IIe Cour de droit civil
du Tribunal fédéral suisse
Le Président : von Werdt
La Greffière : Hildbrand