Faits : A. Ressortissant camerounais né en 1974, A.X._ est arrivé en Suisse en décembre 2002 pour y déposer une demande d'asile, laquelle a été rejetée le 15 juillet 2003. Le 27 avril 2007, il a épousé Y._, ressortissante suisse née en 1958, et a obtenu de ce fait une autorisation de séjour au titre du regroupement familial dans le canton de Vaud, laquelle a été renouvelée pour la dernière fois jusqu'au 26 avril 2012. Aucun enfant n'est issu de cette union. Par convention ratifiée le 11 juin 2010 par la présidente du Tribunal d'arrondissement de Lausanne pour valoir prononcé de mesures protectrices de l'union conjugale, les époux X._ sont convenus de vivre séparés pour une durée indéterminée. Par courrier du 10 juin 2011, le Service de la population du canton de Vaud (ci-après: Service de la population) a communiqué à A.X._ son intention de révoquer son autorisation de séjour et lui a accordé le droit d'être entendu. L'intéressé a exercé son droit d'être entendu par courrier du 14 septembre 2011 pour s'opposer à la révocation de son autorisation de séjour. Par courrier du 16 juillet 2012, le Service de la population a informé A.X._ que les conditions liées à son autorisation de séjour obtenue à la suite de son mariage n'étaient plus remplies. Il s'est toutefois déclaré favorable à la poursuite du séjour en Suisse de l'intéressé dès lors que son comportement n'avait pas donné lieu à des plaintes, que la vie commune du couple avait duré plus de trois ans et que l'intégration de l'intéressé paraissait réussie. Le 2 octobre 2012, le Service de la population a transmis le dossier à l'Office fédéral des migrations (devenu entretemps le Secrétariat d'Etat aux migrations; ci-après: le SEM) afin qu'il donne son approbation à la prolongation de l'autorisation de séjour en application de l'art. 50 LEtr. B. Par décision du 7 mai 2013, le SEM a refusé d'approuver la prolongation de l'autorisation de séjour de A.X._ et prononcé son renvoi de Suisse. Par arrêt du 16 novembre 2015, le Tribunal administratif fédéral a rejeté le recours que l'intéressé avait interjeté contre la décision du SEM. C. A l'encontre de cet arrêt, A.X._ dépose un recours en matière de droit public au Tribunal fédéral. Il conclut, sous suite de frais et dépens, principalement, à l'annulation de l'arrêt attaqué et à ce qu'une autorisation de séjour lui soit délivrée. Subsidiairement, il demande au Tribunal fédéral de renvoyer la cause au Tribunal administratif fédéral pour nouvelle décision. Il requiert en outre le bénéfice de l'assistance judiciaire. Le Tribunal administratif fédéral a renoncé à déposer des observations. Le SEM a conclu au rejet du recours. Par ordonnance du 14 janvier 2016, le Président de la IIe Cour de droit public a admis la requête d'effet suspensif.