Faits : A. Par jugement du 9 mars 2016, le Tribunal de police de Genève a acquitté X._ des chefs 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 d'interdiction de pénétrer dans une région déterminée (art. 119 LEtr). Il s'est vu allouer des indemnités en réparation du tort moral subi et en couverture de ses frais de défense. B. Par arrêt du 4 août 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 interjeté par le Ministère public contre le jugement de première instance, qu'elle a annulé. Elle a reconnu X._ coupable d'infractions aux art. 115 al. 1 let. b et 119 al. 1 LEtr et l'a condamné à une courte peine privative de liberté de 30 jours, sous déduction de la détention subie, cette peine étant complémentaire à celle prononcée le 6 septembre 2015 par le Ministère public. En substance, il est reproché à X._, d'origine mauritanienne, d'avoir, à Genève, du 15 janvier au 12 mars 2015, séjourné en Suisse alors qu'il était démuni d'un passeport valable et d'une autorisation de séjour et faisait l'objet d'une décision de renvoi entrée en force le 8 octobre 2014. Il lui est également reproché d'avoir, à tout le moins le 12 mars 2015, pénétré sur le territoire genevois, alors qu'il était frappé d'une interdiction d'accès à ce canton, dûment notifiée, valable du 16 décembre 2014 au 16 décembre 2015. C. X._ forme un recours en matière pénale auprès du Tribunal fédéral contre l'arrêt cantonal et conclut à son acquittement. Subsidiairement, il conclut au renvoi de la cause à la cour cantonale pour qu'elle statue dans le sens des considérants. Il sollicite en outre le bénéfice de l'assistance judiciaire.