Faits: A. A._ est propriétaire de la parcelle n° 104 de la commune de Nendaz, située au lieu-dit Lavantier, en contrebas de la route de Siviez. Ce bien-fonds comprend un accès carrossable desservant les parcelles n° 59 et n° 60, propriétés de l'intéressé, respectivement de son père. Il est classé en zone sans affectation spéciale selon le plan de zone de la commune et est constitué de 1'661 m2 de surfaces pâturées. B. Le 18 août 2008, la Commune de Nendaz a constaté que des travaux de construction (radier en béton sur lequel reposaient quatre murs de briques percés d'ouvertures pour portes et fenêtres) avaient été entrepris sans autorisation sur la parcelle n° 104. Elle a interpellé A._ afin qu'il se détermine sur la nature de ces travaux et l'a informé de la nécessité de déposer un dossier d'autorisation de construire. Par courrier du 3 septembre 2008, celui-ci a expliqué que suite à l'affaissement d'une partie de la route d'accès, des dégâts avaient été occasionnés à un ouvrage (fondations d'une étable non achevée), situé immédiatement en contrebas, érigé par son grand-père entre 1959 et 1960; il aurait entrepris ces travaux afin de sécuriser les lieux et maintenir cette construction en l'état. Il envisageait en outre de déposer une demande d'autorisation tendant à la pose d'une dalle ou d'un toit sur la construction afin de condamner le trou béant situé juste au-dessous du chemin d'accès. Le 15 décembre 2008, la Commission cantonale des constructions du canton du Valais (ci-après: la CCC) a estimé qu'aucune autorisation de construire ne pouvait être octroyée et a ordonné la démolition de l'ouvrage existant ainsi que la remise en état du profil et de la végétation du terrain, dans un délai de six mois dès l'entrée en force de sa décision. Le 26 mai 2010, le Conseil d'Etat valaisan a rejeté le recours déposé par l'intéressé et a confirmé la décision de la CCC. C. Par arrêt du 14 octobre 2010, la Cour de droit public du Tribunal cantonal valaisan (ci-après: le Tribunal cantonal) a rejeté le recours formé par A._ au motif que la construction en cause, non conforme à l'affectation de la zone, ne pouvait bénéficier ni d'une autorisation ordinaire au sens de l'art. 22 LAT, ni d'une autorisation dérogatoire au sens des art. 24 ss LAT; l'ordre de démolition et de remise en état des lieux ne violait en outre pas le principe de la proportionnalité. D. Par mémoire de recours du 25 novembre 2010, A._ demande l'annulation de l'arrêt cantonal. Le Tribunal cantonal et la CCC renoncent à se déterminer. Le Conseil d'Etat se réfère à l'arrêt attaqué et propose le rejet du recours. L'Office fédéral du développement territorial indique que l'affaire ne soulève pas, au regard du droit fédéral de l'aménagement du territoire et de la planification, des questions de principe nécessitant des observations de sa part. La Commune de Nendaz ne s'est pas déterminée. Le recourant a répliqué.