Faits: A. X._, né en 1972, et son épouse Y._, née en 1980, ont déposé une demande d'asile en Suisse pour eux-mêmes et leur enfants le 11 septembre 1998. Entendu dans le cadre de la procédure d'asile, X._ a déclaré être de nationalité irakienne, avoir quitté l'Irak en 1980 et avoir vécu depuis lors en Syrie d'où il était venu demander l'asile en Suisse. Quant à Y._, elle a déclaré être également de nationalité irakienne mais née en Syrie. Dans le cadre de cette procédure, les époux X._ ont été soumis à un examen linguistique et de provenance. Selon les conclusions de cet examen, le pays de socialisation qui a le plus marqué les deux époux n'est pas l'Irak mais la Syrie. Les époux X._ ont alors expliqué avoir longtemps vécu dans la clandestinité en Syrie et n'avoir pas pratiqué la langue de leur pays d'origine. Par décision du 2 octobre 2000, l'Office fédéral des migrations (ci-après ODM) n'est pas entré en matière sur les demandes d'asile des époux X._ et a prononcé leur renvoi de Suisse. La Commission suisse de recours en matière d'asile a rejeté en date du 20 avril 2005 le recours interjeté par les époux X._. Le 26 janvier 2006, l'ODM a reconsidéré sa décision et prononcé l'admission provisoire des époux X._ et de leurs enfants, en considération de leur situation et des conditions générales de sécurité en Syrie. Le 1er octobre 2008, les époux X._ et leurs enfants ont été mis au bénéfice d'une autorisation de séjour. B. Le 3 février 2010, les époux X._ ont adressé à l'ODM une demande tendant à obtenir le statut d'apatride pour eux-mêmes et leurs enfants, requête à l'appui de laquelle ils ont exposé qu'ils étaient de nationalité irakienne mais que ni l'Ambassade d'Irak, ni l'Ambassade de Syrie n'étaient disposées à leur délivrer des documents d'identité nationaux. Par décision du 20 mai 2010, l'ODM a rejeté la demande des époux X._. Le 11 juillet 2011, le Tribunal administratif fédéral a rejeté le recours que les époux X._ avaient déposé à l'encontre de la décision de l'ODM. Il a relevé en substance que les démarches des époux X._ auprès des autorités irakiennes et syriennes ne sauraient suffire à leur voir reconnaître le statut d'apatride, de sorte que c'est de manière parfaitement fondée que l'ODM avait rejeté leur demande tendant à la reconnaissance du statut d'apatride. C. Par acte du 15 août 2011, les époux X._ ont adressé un recours en matière de droit public au Tribunal fédéral. Ils concluent à l'admission du recours, à l'annulation de l'arrêt du Tribunal administratif fédéral du 11 juillet 2011 et à la reconnaissance du statut d'apatride pour eux-mêmes et leurs cinq enfants, des pièces de légitimation leur étant établies en conséquence. Ils demandent en outre à bénéficier de l'assistance judiciaire et à être dispensés de verser une avance de frais. Subsidiairement, ils concluent au renvoi de la cause à l'autorité inférieure pour qu'elle statue à nouveau dans le sens des considérants. Le 5 octobre 2011, l'ODM a conclu au rejet du recours en renvoyant aux considérants du Tribunal administratif fédéral. 