Faits : A. Par jugement du 20 juillet 2015, le Tribunal de police de Genève a acquitté B._ du chef d'infraction à l'art. 19 al. 1 de la loi fédérale sur les stupéfiants et les substances psychotropes du 3 octobre 1951 (LStup; RS 812.121), l'a reconnu coupable de séjour illégal au sens de l'art. 115 al. 1 let. b de la loi fédérale sur les étrangers du 16 décembre 2005 (LEtr; RS 142.20) et l'a condamné à une peine pécuniaire de 70 jours-amende, d'un montant de 10 fr. l'unité, sous déduction de la détention subie avant jugement. B. Statuant sur recours du ministère public portant sur l'infraction à la LStup, la Cour de justice genevoise, Chambre pénale d'appel et de révision, l'a rejeté par arrêt du 8 février 2016. Elle a en outre réformé le jugement de première instance d'office (art. 404 al. 2 CPP), et a libéré B._ des fins de la poursuite, en particulier s'agissant de l'infraction de séjour illégal. L'arrêt repose en substance sur les faits suivants. B._, ressortissant guinéen, a séjourné en Suisse, du 15 décembre 2013 au 17 octobre 2014, puis du 1 er décembre 2014 au 12 mars 2015, alors qu'il ne disposait pas des autorisations requises et était démuni de documents d'identité ainsi que de moyens de subsistance. B._ est enregistré en Suisse depuis le 30 juillet 2010 et a été débouté de sa requête d'asile. A teneur d'un courriel du 8 avril 2015 du Service de la population vaudois, B._ faisait l'objet d'une décision de renvoi en force, mais il n'était pas possible d'organiser son renvoi car le Secrétariat d'État aux migrations (ci-après: SEM) n'avait pas obtenu de laissez-passer et le canton de Vaud, après avoir annoncé la disparition de l'intéressé, avait cessé son soutien à l'obtention de documents. Il s'est vu remettre un bon de sortie valable du 15 octobre au 14 décembre 2013. B._ a reconnu l'irrégularité de son séjour du 15 décembre 2013 au 17 octobre 2014 et du 1 er décembre 2014 au 12 mars 2015. C. Le Ministère public genevois forme un recours en matière pénale auprès du Tribunal fédéral contre l'arrêt du 8 février 2016 et conclut à ce que B._ est reconnu coupable de séjour illégal au sens de l'art. 115 al. 1 let. b LEtr et condamné à une peine pécuniaire de 70 jours-amende, d'un montant de 10 fr. l'unité, sous déduction de la détention avant jugement. Le recours porte sur la seule infraction à la LEtr, à l'exclusion de l'infraction à la LStup. Invité à se déterminer sur le mémoire de recours, B._ a conclu, avec suite de frais et dépens, à son rejet et à la confirmation de l'arrêt cantonal. Il sollicite le bénéfice de l'assistance judiciaire. La cour cantonale a renoncé à se prononcer sur le mémoire de recours et s'est référée à son arrêt.