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.

Considérant en droit :
1.
Dirigé contre une décision finale (<ref-law>) prise en dernière instance cantonale (art. 86 al. 1 let. d LTF) dans le domaine du droit public des constructions (<ref-law>), le recours est en principe recevable comme recours en matière de droit public, aucune des exceptions prévues à l'<ref-law> n'étant réalisée. La recourante a pris part à la procédure de recours devant le Tribunal cantonal. En tant que propriétaire du mazot litigieux et destinataire de l'ordre de remise en état, elle est particulièrement touchée par l'arrêt attaqué et peut ainsi se prévaloir d'un intérêt digne de protection à son annulation. Elle a donc qualité pour recourir au sens de l'<ref-law>.
2.
Dans leurs observations respectives des 17 mai et 13 septembre 2016, les parties s'étendent longuement sur la façon et la fréquence avec lesquelles la recourante procède à la fauche du pré situé sur sa parcelle: alors que la recourante prétend se charger essentiellement seule de cette tâche, l'intimée affirme le contraire, soutenant que celle-ci serait exclusivement assurée par un tiers agriculteur. Ces allégations sont irrecevables dans la mesure où elles s'écartent des constatations cantonales sans que les parties ne se plaignent pour autant d'arbitraire dans l'établissement des faits (cf. <ref-law> et 106 al. 2 LTF); le Tribunal fédéral s'en tiendra à l'état de fait cantonal (<ref-law>).
3.
Dans un premier grief, la recourante soutient que les conditions d'une autorisation ordinaire au sens des art. 16a et 22 LAT seraient en l'espèce réalisées. Elle estime en particulier que le fauchage du pré sur sa parcelle constituerait une activité agricole au sens de l'art. 3 de la loi fédérale sur l'agriculteur du 29 avril 1998 (LAgr; RS 910.1); le mazot litigieux répondrait, selon elle, aux besoins de cette activité au sens de l'art. 34 de l'ordonnance sur l'aménagement du territoire du 28 juin 2000 (OAT; RS 700.1).
3.1. En vertu de l'<ref-law>, les mémoires de recours doivent être motivés. Selon l'<ref-law>, les motifs doivent exposer succinctement en quoi l'acte attaqué viole le droit. Pour satisfaire à cette exigence, il appartient au recourant de discuter au moins brièvement les considérants de la décision litigieuse (<ref-ruling> consid. 2.1 p. 245). Il doit exister un lien entre la motivation et la décision litigieuse. Lorsque le mémoire de recours consiste à reprendre mot pour mot devant le Tribunal fédéral la même motivation que celle présentée devant l'instance inférieure, un tel lien n'existe pas et le recours est inadmissible sous l'angle de l'<ref-law> (<ref-ruling> consid. 2.3 p. 246).
3.2. Se référant notamment aux préavis négatifs du SCA et du SDT, la cour cantonale a estimé que la construction du mazot était contraire à l'affectation de la zone, la recourante n'exerçant pas d'activité agricole sur sa parcelle (cf. art. 16a al. 1 LAT). A cet égard, le Tribunal cantonal a considéré qu'il était indifférent - contrairement à ce que soutenait la recourante - de savoir si le fauchage du pré devait être assimilé à une activité agricole au sens de l'<ref-law>; il a précisé qu'au regard de la jurisprudence (citant l'arrêt 1A.256/2005 du 10 mars 2006 consid. 2.2) la notion d'exploitation agricole au sens de la LAT (cf. art. 16a LAT et 34 OAT) répondait à des critères différents - non réalisés en l'espèce - de ceux découlant du champ d'application de la LAgr. La cour cantonale s'est enfin fondée sur le fait que le fauchage annuel de la parcelle était confié à un agriculteur professionnel pour nier l'existence d'une exploitation agricole. Dans ce contexte, le Tribunal cantonal a jugé que le mazot ne pouvait bénéficier d'une autorisation ordinaire au sens des art. 16a et 22 LAT.
La recourante ne développe aucune argumentation en lien avec ces motifs, en particulier, s'agissant de la distinction entre la notion d'exploitation agricole, au sens de l'aménagement du territoire, et celle d'agriculture, selon la LAgr, distinction sur laquelle se fonde pourtant l'essentiel du refus d'une autorisation ordinaire. La recourante se contente, à l'appui de son grief, de reprendre mot pour mot l'argumentation développée sans succès devant le Tribunal cantonal. Une telle manière de procéder n'est pas admissible au regard des exigences de l'<ref-law> (cf. <ref-ruling> consid. 2.3 p. 246). Dans ces conditions, il convient, en ce qui concerne l'application des art. 16a et 22 LAT, de renvoyer aux considérants pertinents de l'arrêt attaqué (<ref-law>).
4.
Examinant également la situation à la lumière du régime dérogatoire prévu par l'art. 24 LAT, le Tribunal cantonal a exclu que le mazot litigieux puisse en bénéficier. La recourante conteste cette appréciation.
4.1. En vertu de l'art. 24 LAT, une autorisation dérogatoire peut être délivrée pour de nouvelles constructions ou installations hors de la zone à bâtir lorsque l'implantation de ces constructions ou installations est imposée par leur destination (let. a) et qu'aucun intérêt prépondérant ne s'y oppose (let. b).
Selon la jurisprudence, une construction est imposée par sa destination au sens de l'art. 24 let. a LAT lorsqu'elle est adaptée aux besoins qu'elle est censée satisfaire et qu'elle ne peut remplir son rôle que si elle est réalisée à l'endroit prévu: une nécessité particulière, tenant à la technique, aux conditions d'exploitation d'une entreprise, ou encore à la configuration ou à la nature du sol, doit imposer le choix de l'endroit. De même, l'implantation hors de la zone à bâtir peut se justifier si l'ouvrage en question ne peut être édifié à l'intérieur de celle-ci en raison des nuisances qu'il occasionne (ouvrage négativement imposé par sa destination, cf. à ce sujet ZEN-RUFFINEN/GUY-ECABERT, Aménagement du territoire, construction, expropriation, 2001, n. 575 p. 267). Seuls des critères particulièrement importants et objectifs sont déterminants, à l'exclusion de points de vue subjectifs du constructeur ou de motifs de convenance personnelle (cf. <ref-ruling> consid. 2.1 p. 218; <ref-ruling> consid. 3.1. p. 68; <ref-ruling> consid. 5a p. 261). L'application de la condition de l'art. 24 let. a LAT doit être stricte, dès lors que cette dernière contribue à l'objectif de séparation du bâti et du non-bâti (cf. <ref-ruling> consid. 4a p. 256; <ref-ruling> consid. 4a p. 281, 379 consid. 3a p. 383; arrêt 1C_877/2013 du 31 juillet 2014 consid. 3.1.1; voir également RUDOLF MUGGLI, Commentaire LAT, 2010, n. 3 ad art. 24 LAT).
4.2. Il n'est en l'espèce pas contesté que le mazot sert actuellement à l'entreposage de l'outillage destiné à l'entretien du pré: une tondeuse à gazon de dimension standard, une faux, une débroussailleuse à essence, un piolet, une scie à bois (à main) et quelques outils de jardinage et d'entretien des buissons. On ne saurait toutefois en déduire - comme le fait la recourante - que l'implantation de la construction litigieuse en zone agricole serait de ce fait imposée par sa destination, comme l'exige l'art. 24 let. a LAT. La recourante perd en effet de vue qu'il n'est pas suffisant, sous l'angle de cette disposition, que le dépôt litigieux présente un lien avec l'entretien de la parcelle, encore faut-il que son implantation sur celle-ci réponde à une nécessité particulière excluant qu'il ne puisse prendre place ailleurs. A cet égard, le seul éloignement - au demeurant non établi - de la zone à bâtir, dans laquelle pourrait prendre place le mazot, n'implique pas automatiquement l'existence d'une telle nécessité et l'arrêt 1C_169/2012 du 19 mars 2013, dont se prévaut la recourante, ne dit pas autre chose: portant sur la question du logement indispensable à l'exploitation agricole au sens de l'<ref-law>, ce précédent rappelle que la proximité de la zone constructible constitue un critère parmi d'autres dans l'examen du caractère nécessaire de l'implantation du logement de l'agriculteur hors de la zone à bâtir, au sein de son domaine (cf. arrêt 1C_169/2012 précité consid. 5.1; cf. également <ref-ruling> consid. 3a p. 69). Or, pour peu que les principes dégagés de cette jurisprudence soient également applicables en l'absence - comme en l'espèce - d'une exploitation agricole (cf. consid. 3.2), force est de reconnaître que l'existence d'une telle nécessité n'est pas établie; on ne discerne en particulier pas en quoi l'outillage concerné - relativement peu encombrant - ne pourrait pas être entreposé ailleurs, quitte à être transporté en cas de besoin, comme cela a - de l'aveu de la recourante - été le cas jusqu'à présent. Dans ces circonstances, en tant qu'il retient que l'implantation choisie repose exclusivement sur des motifs de convenance personnelle, l'arrêt attaqué n'est pas discutable.
On ne saurait enfin suivre la recourante lorsqu'elle affirme qu'un mazot ne pourrait, de par sa nature traditionnelle, être implanté qu'en dehors de la zone à bâtir. Outre que rien ne permet de confirmer cette affirmation, le choix d'une forme particulière de construction ne saurait faire obstacle à l'application du principe cardinal de la séparation du territoire bâti et non bâti et justifier une implantation en zone agricole ne répondant - comme le mazot en cause - à aucune nécessité au sens de la jurisprudence.
4.3. Entièrement mal fondé, ce grief doit être rejeté.
5.
Le dépôt litigieux ne pouvant être mis au bénéfice d'une autorisation postérieure, il convient d'examiner si l'ordre de remise en état est conforme au principe de la proportionnalité, ce que la recourante conteste.
5.1. Selon une jurisprudence bien établie, lorsque des constructions ou des installations illicites sont réalisées en dehors de la zone à bâtir, le droit fédéral exige en principe que soit rétabli un état conforme au droit. L'autorité renonce à une telle mesure, conformément au principe de la proportionnalité, si les dérogations à la règle sont mineures, si l'intérêt public lésé n'est pas de nature à justifier le dommage que la démolition causerait au maître de l'ouvrage, si celui-ci pouvait de bonne foi se croire autorisé à construire ou encore s'il y a des chances sérieuses de faire reconnaître la construction comme conforme au droit (<ref-ruling> consid. 6 p. 35; <ref-ruling> consid. 3a/bb p. 252). Celui qui place l'autorité devant un fait accompli doit s'attendre à ce que celle-ci se préoccupe plus de rétablir une situation conforme au droit que d'éviter les inconvénients qui en découlent pour lui (ATF <ref-ruling> consid. 4a p. 255; <ref-ruling> consid. 6b p. 224).
5.2. En l'espèce, la cour cantonale a jugé que la dérogation à la règle ne pouvait être qualifiée de mineure. Elle a retenu que la recourante avait agi de mauvaise foi en érigeant le mazot tout en sachant que celui-ci ne pouvait bénéficier d'une autorisation suite, notamment, aux renseignements communiqués par la CCC. Le Tribunal cantonal a en outre considéré que cette construction ne reposait sur aucun motif objectif propre à justifier une dérogation au caractère inconstructible de la zone agricole. L'instance précédente a enfin estimé que la recourante n'avait pas démontré que le coût lié au déplacement du mazot serait disproportionné par rapport aux intérêts publics poursuivis, en particulier celui lié à la séparation du territoire bâti et non bâti.
La recourante conteste cette appréciation. On ne discerne cependant pas en quoi il serait critiquable - et la recourante ne l'explique pas - d'avoir retenu qu'elle a agi de mauvaise foi en érigeant sans autorisation le mayen litigieux: la recourante a non seulement fait fi de la réponse négative de la CCC à sa demande de renseignement du 30 octobre 2013 (cf. art. 30 de l'ordonnance sur les constructions du 2 octobre 1996 [OC; RS/VS 705.100), mais également du refus du permis de construire alors encore débattu devant le Conseil d'Etat. Par ailleurs, comme on l'a vu, l'implantation du mazot hors de la zone à bâtir ne répond pas à une nécessité particulière, mais repose, au contraire, sur des motifs de convenance personnelle tenant aux désagréments liés au transport de l'outillage de jardin (cf. consid. 4.2). Enfin, tout comme devant l'instance précédente, la recourante ne fournit aucun élément concret susceptible de démontrer le caractère disproportionné du coût de la remise en état, se contentant d'affirmer, de façon purement appellatoire, qu'il s'agirait d'une "somme conséquente", ce qui est insuffisant au regard des exigences de motivation du recours fédéral (art. 42 al. 2 et 106 al. 2 LTF). Dans ces circonstances, la recourante devait s'attendre à ce que l'autorité favorise le respect du caractère inconstructible de la zone et fasse prévaloir l'intérêt public lié au respect de la séparation entre le territoire bâti et non bâti sur son intérêt privé au maintien de la construction illicite.
5.3. Mal fondé, ce grief doit être écarté pour autant que recevable.
6.
Sur le vu de ce qui précède, le recours doit être rejeté dans la mesure de sa recevabilité, aux frais de la recourante, qui succombe (art. 65 et 66 al. 1 LTF). Il n'y a pas lieu d'allouer des dépens à l'intimée, qui a procédé sans avocat (art. 68 al. 1 et 2 LTF; <ref-ruling> consid. 4 p. 446).

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est rejeté dans la mesure où il est recevable.
2.
Le frais judiciaires, arrêtés à 3'000 fr., sont mis à la charge de la recourante.
3.
Il n'est pas alloué de dépens.
4.
Le présent arrêt est communiqué à la mandataire de la recourante, à Pro Natura Valais, à la Commune d'Icogne, au Conseil d'Etat du canton du Valais ainsi qu'au Tribunal cantonal du canton du Valais, Cour de droit public, et à l'Office fédéral du développement territorial.
Lausanne, le 20 octobre 2016
Au nom de la Ire Cour de droit public
du Tribunal fédéral suisse
Le Juge présidant : Karlen
Le Greffier : Alvarez