Faits : A. X._, ressortissant gambien né en 1983, a déposé une demande d'asile en Suisse le 6 octobre 2005 sous une fausse identité. Par décision du 27 octobre 2005, l'Office fédéral des migrations (actuellement le Secrétariat d'Etat aux migrations; ci-après: le Secrétariat d'Etat) n'est pas entré en matière sur cette demande et a prononcé le renvoi et l'exécution du renvoi de l'intéressé. Malgré cette décision, X._ est resté en Suisse où, entre avril 2006 et janvier 2007, il a été condamné à quatre reprises à un total de 55 jours de peine privative de liberté et dix jours-amende, essentiellement pour des infractions à la LStup (RS 812.121). Par décision du 4 avril 2007, le Secrétariat d'Etat a prononcé une interdiction d'entrée en Suisse à l'encontre de l'intéressé, valable jusqu'au 3 avril 2012. Le 1 er juin 2007, X._ a encore été condamné à 30 jours-amende pour recel. Le 16 mai 2008, l'intéressé s'est marié avec une ressortissante suisse née en 1984. Il a été mis au bénéfice d'une autorisation de séjour au titre du regroupement familial. Deux enfants sont issus de cette union (2008 et 2010). Le 2 octobre 2008, le Secrétariat d'Etat a annulé l'interdiction d'entrée en Suisse de X._ et l'a averti qu'en cas de nouvelles plaintes fondées, de sévères mesures administratives pourraient être prononcées à son encontre. Après avoir encore été condamné à trois reprises, en particulier pour des infractions graves à la LCR et opposition aux actes de l'autorité, X._, par jugement du 3 décembre 2013, a été reconnu coupable d'infraction grave à la LStup et condamné à quatre ans de peine privative de liberté. Ce jugement a été confirmé sur recours, en dernier lieu le 27 octobre 2014 par le Tribunal fédéral (arrêt 6B_632/2014). B. Par décision du 31 août 2015, l'Office cantonal de la population et des migrations de la République et canton de Genève (ci-après: l'Office cantonal) a refusé de prolonger l'autorisation de séjour de X._ et de lui délivrer une autorisation d'établissement dont ce dernier avait sollicité l'octroi le 18 mai 2015. Cet office a en outre prononcé le renvoi de l'intéressé. Le 30 septembre 2015, celui-ci a contesté ce prononcé auprès du Tribunal administratif de première instance de la République et canton de Genève, qui a confirmé la décision de l'Office cantonal par jugement du 28 janvier 2016. Par acte du 29 février 2016, X._ a interjeté recours contre ce jugement auprès de la Chambre administrative de la Cour de justice de la République et canton de Genève (ci-après: la Cour de justice). Par arrêt du 3 mai 2016, la Cour de justice a admis le recours de X._ et l'a averti que s'il devait commettre de nouvelles infractions pénales, il s'exposerait à des mesures d'éloignement. Elle a jugé en bref que s'il remplissait les conditions posées à la révocation d'une autorisation de séjour, sa situation familiale, c'est-à-dire la présence en Suisse de sa femme et de ses deux enfants, tous trois ressortissants helvétiques, faisait obstacle à une telle révocation. Un renvoi de Suisse violerait l'art. 8 CEDH et constituerait une mesure disproportionnée. C. Agissant par la voie du recours en matière de droit public, le Secrétariat d'Etat demande en substance au Tribunal fédéral, d'annuler l'arrêt du 3 mai 2016 de la Cour de justice et de ne pas prolonger l'autorisation de séjour de X._. Il se plaint de violation du droit fédéral et international. La Cour de justice persiste dans les considérants et le dispositif de son arrêt. L'Office cantonal renonce à se déterminer. X._ demande au Tribunal fédéral, sous suite de frais et dépens, outre l'assistance judiciaire, de rejeter le recours. Invité par le Tribunal fédéral le 12 octobre 2016 à présenter de manière appropriée et complète sa situation financière et celle de son épouse, le recourant ne s'est pas déterminé. Dans des observations finales, le Secrétariat d'Etat a confirmé ses conclusions.