Faits : A. Par jugement du 23 janvier 2015, le Tribunal de police de Genève a reconnu A._ coupable du chef de séjour illégal (art. 115 al. 1 let. b de la loi fédérale du 16 décembre 2005 sur les étrangers, [LEtr; RS 142.20]) et l'a condamné à une peine privative de liberté d'ensemble de 60 jours, comprenant le solde de peine de 29 jours découlant de la révocation de la libération conditionnelle accordée le 25 mars 2014 (pour entrée et séjour illégal), sous déduction de la détention subie avant jugement. B. Par arrêt du 2 février 2016, la Cour de justice de la République et canton de Genève, Chambre pénale d'appel et de révision, a admis l'appel formé par A._ contre la décision de première instance et l'a acquitté du chef de séjour illégal. L'arrêt repose en substance sur les faits suivants. A._, ressortissant guinéen, a séjourné du 9 avril au 2 mai 2014, puis du 4 mai au 18 septembre 2014 sur le territoire suisse, en étant démuni de papiers d'identité, des autorisations et des moyens de subsistance nécessaires. Sa demande d'asile du 3 mars 2004 a fait l'objet d'une décision de non-entrée en matière du 12 mai 2004, entrée en force le 23 mai 2004. Il a été attribué au canton de Neuchâtel, dont les autorités ont indiqué n'avoir entamé aucune démarche en vue de l'exécution du renvoi, puisqu'il avait disparu des structures d'asile de leur canton le 4 juin 2004. Entendu par le Ministère public, A._ a exposé vivre en Suisse depuis 2004 et vouloir y rester, n'ayant aucun autre endroit où aller. 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 cantonal et conclut à sa réforme en ce sens que A._ est reconnu coupable de séjour illégal et condamné à une peine privative de liberté d'ensemble de 60 jours, sous déduction de la détention avant jugement. Invité à se déterminer sur le recours, A._ 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 déterminer en se référant à son arrêt.