Faits : A. Le Syndicat autonome des postiers (ci-après: le SAP) est une association de droit privé créée en 2005, dont le but statutaire est l'amélioration des conditions professionnelles de ses membres. Le 5 mars 2012, le SAP s'est adressé à La Poste Suisse pour lui demander d'être intégré aux négociations relatives à la conclusion d'une nouvelle convention collective de travail. Le 3 avril 2012, la Poste Suisse a refusé d'accéder à cette demande, au motif que le SAP n'était pas représentatif. Le 29 avril 2013, le SAP a saisi la Commission fédérale de la poste (ci-après: la PostCom) d'une plainte, sollicitant qu'elle rende une décision formelle quant à l'obligation de La Poste Suisse de l'intégrer aux négociations collectives menées en vue de la conclusion d'une convention collective de travail. Dans sa prise de position du 7 juin 2013, La Poste Suisse a indiqué qu'elle considérait que la PostCom n'était pas l'autorité compétente pour rendre une décision dans ce domaine et qu'elle ne devait donc pas entrer en matière sur la plainte du SAP. La Poste Suisse était un établissement de droit public disposant de la personnalité juridique jusqu'au 25 juin 2013. Elle a été transformée en société anonyme de droit public sous la raison sociale "La Poste Suisse SA" (ci-après: La Poste Suisse) dès le 26 juin 2013. B. Le 4 juillet 2013, la PostCom a décidé de ne "pas donner pour instruction à La Poste Suisse SA de mener des négociations avec le SAP". Le SAP a interjeté recours contre cette décision auprès du Tribunal administratif fédéral le 22 juillet 2013, concluant principalement à son annulation et à ce qu'il ordonne à La Poste Suisse de l'intégrer aux négociations de la prochaine convention collective de travail. A titre de mesures provisionnelles, il requérait le droit de pouvoir participer aux premières séances de négociations, qui devaient débuter à la mi-août 2013. Cette requête a été rejetée par le Tribunal administratif fédéral par décision incidente du 14 août 2013, qui n'a pas fait l'objet d'un recours. Dans son arrêt du 13 décembre 2013, le Tribunal administratif fédéral a retenu que la PostCom n'avait pas la compétence matérielle d'enjoindre La Poste Suisse d'intégrer un syndicat à des négociations collectives et que cette autorité n'aurait donc pas dû entrer en matière sur la plainte du SAP. Il a en conséquence annulé la décision du 4 juillet 2013 de la PostCom et rejeté le recours du SAP pour le surplus. C. Agissant par la voie du recours en matière de droit public, le SAP demande au Tribunal fédéral, sous suite de frais et dépens, préalablement, d'annuler l'arrêt du 13 décembre 2013 du Tribunal administratif fédéral; principalement, de dire que la PostCom était compétente pour rendre la décision sollicitée, d'annuler la décision de de cette autorité du 4 juillet 2013, d'ordonner à La Poste Suisse de l'intégrer aux négociations de la prochaine convention collective de travail et de débouter cette dernière de toutes autres ou contraires conclusions; subsidiairement, de dire que la PostCom était compétente pour rendre la décision sollicitée, d'annuler la décision de cette autorité du 4 juillet 2013, de renvoyer la cause au Tribunal administratif fédéral pour nouvelle décision dans le sens des considérants et de débouter La Poste Suisse de toutes autres ou contraires conclusions; dans tous les cas, de permettre au SAP de prouver la véracité des faits allégués dans son écriture et de débouter La Poste Suisse de toutes autres ou contraires conclusions. La Poste Suisse a déposé une réponse au recours et a conclu à son rejet, sous suite de frais et dépens. La PostCom, le Département fédéral de l'environnement, des transports, de l'énergie et de la communication, ainsi que le Tribunal administratif fédéral ont renoncé à prendre position.