Faits : A. La communauté héréditaire de feu B._, composée notamment de A._, est propriétaire de la parcelle n° 203, folio 3, du cadastre de la Commune d'Icogne, au lieu-dit "Tsantové". Selon le plan d'affectation des zones (PAZ) et le règlement communal des constructions (RCC), votés le 21 août 2000 et approuvés par le Conseil d'Etat du canton du Valais le 27 novembre 2001 ce bien-fonds est classé en zone agricole II et en zone de protection de la nature d'importance cantonale. D'une surface de 4'012 m 2, il supporte la résidence principale des hoirs et se compose en outre d'un pré de 3'869 m 2. Le 30 octobre 2013, A._ a adressé à la Commission cantonale des constructions (ci-après: CCC) une demande de renseignements portant sur la construction, sur cette parcelle, d'un "dépôt en forme de mazot" de 27 m 3 destiné à l'entreposage des outils nécessaires à l'entretien du pré. Le 9 décembre 2013, la CCC a répondu que, de son point de vue, le projet ne poursuivait pas un but agricole et n'était lié à aucune exploitation agricole; une autorisation au sens des art. 16a et 22 de la loi fédérale sur l'aménagement du territoire du 22 juin 1979 (LAT; RS 700) n'était partant pas envisageable et serait refusée en cas de demande. B. Le 14 février 2014, agissant en qualité de représentante de la communauté héréditaire, A._ a déposé une demande d'autorisation de construire pour l'édification d'un mazot d'un volume de 27 m 3 (3,64 m de large, 3,63 m de long et d'une hauteur de 4 m). Mis à l'enquête public, ce projet a suscité, le 5 mars 2014, l'opposition de Pro Natura Valais au motif que la nouvelle construction projetée en zone agricole II et en zone de protection de la nature d'importance cantonale ne pouvait bénéficier ni d'une autorisation ordinaire (art. 22 LAT) ni d'une autorisation dérogatoire (art. 24 LAT). Le 16 avril 2014, le Service cantonal de l'agriculture (ci-après: SCA) a indiqué que A._ n'exerçait pas une activité agricole reconnue ni ne percevait des paiements directs versés dans l'agriculture (au sens de l'ordonnance du 23 octobre 2013 sur le paiements directs [OPD; RS 910.13]), raisons pour lesquelles il ne se prononçait pas sur la clause du besoin agricole du projet. Le Service du développement territorial (ci-après: SDT) a préavisé négativement le projet, considérant que l'implantation de celui-ci hors de la zone à bâtir n'était pas imposée par sa destination; il a par ailleurs précisé - à l'instar du SCA - qu'aucun besoin agricole ne justifiait la construction. Quant au Service des forêts et du paysage, il a préavisé favorablement le projet, l'implantation du mazot étant prévue hors de la zone de protection de la nature. Par décision du 22 mai 2014, la CCC a refusé le permis de construire. La commission a considéré que le projet ne répondait ni aux conditions d'une autorisation ordinaire (art. 22 LAT) ni à celles du régime dérogatoire de l'art. 24 LAT. Le 23 juin 2014, A._ a recouru contre cette décision au Conseil d'Etat. En cours d'instance, constatant que A._ avait procédé, sans autorisation, à la réalisation du mazot sur la parcelle n° 203, la CCC a ordonné la remise en état des lieux, par décision du 22 janvier 2015. Par acte du 27 février 2015, l'intéressée a également porté cette décision devant le Conseil d'Etat. C. Par décision du 16 septembre 2015, le Conseil d'Etat a ordonné la jonction des causes et a rejeté les recours. Le 22 octobre 2015, A._ s'est pourvue contre cette décision devant la Cour de droit public du Tribunal cantonal du canton du Valais. Par arrêt du 1 er avril 2016, la cour cantonale a rejeté le recours. Elle a en substance considéré que l'entretien du pré ne pouvait être assimilé à une exploitation agricole, de sorte que l'octroi d'une autorisation ordinaire était exclu; dans ce cadre, l'instance précédente a notamment retenu que le fauchage annuel du pré était réalisé par un agriculteur professionnel. Le Tribunal cantonal a en outre nié que le projet remplisse les conditions d'une autorisation dérogatoire. La cour cantonale a enfin jugé que la remise en état n'était pas contraire au principe de la proportionnalité. D. Agissant par la voie du recours en matière de droit public, la recourante demande principalement au Tribunal fédéral de réformer l'arrêt attaqué en ce sens que l'installation d'un mayen sur la parcelle n° 203 est autorisée et l'ordre de remise en état annulé; subsidiairement, elle conclut au renvoi de la cause à l'instance précédente pour nouvelle décision dans le sens des considérants. La recourante requiert en outre l'octroi de l'effet suspensif. Le Tribunal cantonal a renoncé à se déterminer. Le Conseil d'Etat se rallie aux considérants de l'arrêt attaqué et propose le rejet du recours. Pro Natura Valais conclut aussi au rejet. Egalement appelé à se déterminer, l'Office fédéral du développement territoriale ARE se rallie à la décision du Conseil d'Etat ainsi qu'à l'arrêt entrepris. Aux termes d'ultimes observations, la recourante persiste dans ses conclusions. Par ordonnance du 20 mai 2016, le Président de la Ire Cour de droit public a admis la requête d'effet suspensif.