Faits : A. X._, ressortissant tunisien né en 1973, est entré en Suisse en mars 2001 pour y étudier. Le 13 janvier 2009, son autorisation de séjour pour études n'a pas été renouvelée et son renvoi de Suisse a été prononcé. Le 7 juillet 2009, l'intéressé a épousé une ressortissante suisse née en 1981. Il a été mis au bénéfice d'une autorisation de séjour au titre du regroupement familial. Le 4 mars 2010, le couple a eu une fille. Il s'est séparé en 2011. B. Par décision du 10 avril 2014, le Service des migrations de la République et canton de Neuchâtel a prolongé l'autorisation de séjour de X._, sous réserve de l'approbation de l'Office fédéral des migrations (actuellement le Secrétariat d'Etat aux migrations). Le 29 juillet 2014, celui-ci a refusé d'approuver la prolongation de l'autorisation de séjour en faveur de X._ et a prononcé son renvoi de Suisse. L'intéressé a contesté ce prononcé auprès du Tribunal administratif fédéral par acte du 25 août 2014. Par arrêt du 17 février 2016, le Tribunal administratif fédéral a rejeté le recours. Il a jugé en bref que X._ ne disposait ni de l'autorité parentale, ni du droit de garde sur sa fille. S'il semblait certes entretenir un lien affectif particulièrement fort avec celle-ci, il n'entretenait cependant pas de lien économique. De plus, sa situation financière était obérée et il dépendait durablement de l'aide sociale. Il a ainsi exclu toute raison personnelle majeure qui aurait imposé la poursuite du séjour en Suisse. C. Agissant par la voie du recours en matière de droit public, X._ demande au Tribunal fédéral, sous suite de frais et dépens, outre l'effet suspensif et l'assistance judiciaire, d'annuler l'arrêt du Tribunal administratif fédéral du 17 février 2016 et de prolonger son autorisation de séjour; subsidiairement de renvoyer la cause au Tribunal administratif fédéral pour nouvelle décision dans le sens des considérants. Outre un établissement inexact des faits, il se plaint de violation du droit fédéral et international. Par ordonnance du 18 avril 2016, le Président de la IIe Cour de droit public du Tribunal fédéral a admis la demande d'effet suspensif. Le Tribunal administratif fédéral renonce à prendre position. Le Secrétariat d'Etat aux migrations conclut au rejet du recours. Dans des observations finales, X._ a confirmé ses conclusions.