Faits: A. B.X._ est propriétaire de la parcelle n° 7593 du registre foncier de la commune de Fully sise au lieu-dit "Les Epenays". Ce bien-fonds, d'une superficie de 1'503 m2, supporte un bâtiment rural (grange, écurie, silo) dans la zone de plaine entre Châtaignier et Saxé, accessible par la route de Solverse. Il est classé en zone agricole. Le 9 mars 2010, B.X._ et son époux, A.X._, ont sollicité l'autorisation de transformer et agrandir le rural. Le projet consistait à ajouter un bâtiment d'habitation de 4 pièces sur un niveau, avec couvert à voitures attenant au rural existant. Ils ont justifié ce projet par le fait qu'ils exploitaient à titre professionnel 5'500 m2 de surface agricole dans le secteur des Epenays, ce qui leur permettait d'accueillir en dehors des périodes d'estivage un cheptel variant entre 14 et 20 unités de gros bétail (UGB; vaches laitières, pièces de gros bétail, génisses et veaux). L'exploitation de ce domaine sans y disposer d'un lieu de séjour créait, selon eux, des inconvénients pratiques majeurs; de plus, B.X._, gravement accidentée en 2003, devait participer à l'exploitation de la ferme familiale pour les besoins de sa santé. Mis à l'enquête publique, le projet n'a suscité aucune opposition. Dans le cadre de l'instruction, le Service de l'agriculture du canton du Valais (ci-après: le SAgr) a, le 21 mai 2010, préavisé favorablement la demande, relevant qu'il s'agissait d'une exploitation relativement importante gérée de manière autonome depuis plus de 15 ans dans un cadre familial et qui comptait plus d'une unité de main-d'oeuvre standart (UMOS); il a justifié son préavis par le caractère exceptionnel de cette demande, en lien avec la réinsertion sociale d'une personne handicapée pour laquelle le contact avec les animaux était bénéfique. Le 31 mai 2010, le Service du développement territorial (ci-après: le SDT) a préavisé négativement la demande, relevant que le projet n'était pas conforme à la zone agricole. Le 30 juin 2010, la Commission cantonale des constructions du canton du Valais (ci-après: la CCC) a refusé l'autorisation de construire sollicitée. Le Conseil d'Etat valaisan a confirmé cette décision par arrêt du 28 septembre 2011. B. Par arrêt du 16 février 2012, la Cour de droit public du Tribunal cantonal du canton du Valais (ci-après: le Tribunal cantonal) a rejeté le recours formé par les époux contre cette décision. En substance, elle a considéré que le projet d'habitation n'était pas indispensable à l'exploitation agricole; il n'était donc pas conforme à l'affectation de la zone agricole au sens de l'art. 16a LAT. De plus, l'implantation de cet ouvrage hors de la zone à bâtir n'était pas imposée par sa destination et ne pouvait ainsi bénéficier de la dérogation prévue par l'art. 24 LAT. Les recourants ne pouvaient en outre se prévaloir du principe de l'égalité de traitement dans l'illégalité. L'instance précédente a, par ailleurs, renoncé à administrer les offres de preuve formulées par les recourants. C. Agissant par la voie du recours en matière de droit public, les époux X._ demandent au Tribunal fédéral d'annuler l'arrêt entrepris et de renvoyer le dossier à l'instance précédente pour nouvelle décision au sens des considérants. Le Tribunal cantonal et la CCC renoncent à se déterminer. Le Conseil d'Etat conclut au rejet du recours et se réfère aux considérants de l'arrêt entrepris. La Commune de Fully déclare maintenir ses préavis positifs. Invité à se déterminer, l'Office fédéral du développement territorial n'a pas formulé d'observations.