Faits : A. Le 10 juillet 2000, l'autorisation de construire une nouvelle remise agricole sur le fonds 10940 de la Commune de La Chaux-de-Fonds a été délivrée à A._. Après les travaux, la commune a constaté qu'une partie de cette remise était utilisée pour les besoins d'une entreprise d'électricité, ce qui a conduit l'intéressé à demander, en 2002 et 2003, la délivrance des autorisations nécessaires à la mise en conformité. Le 2 juillet 2003, le département compétent a refusé les autorisations requises, interdit l'utilisation de la remise pour un usage non agricole et ordonné l'évacuation du matériel électrique; il a ajouté que l'interdiction et l'ordre d'évacuation seraient mentionnés au registre foncier. Sur recours, le Tribunal administratif a confirmé cette décision, par arrêt du 9 février 2006. B. Le 5 juillet 2013, A._ a requis l'autorisation de transformer une étable existante en stabulation et de l'agrandir par une aire paillée couverte, sur la parcelle 10940; cette demande portait également sur la création de trois boxes à chevaux dans ce bâtiment. Le 28 janvier 2014, le Conseil communal de La Chaux-de-Fonds a octroyé le permis de construire requis; les différentes conditions figurant dans le préavis du 4 décembre 2013 du Service de l'aménagement du territoire ainsi que dans la décision spéciale du 29 novembre 2013 du Département du développement territorial et de l'environnement (ci-après: DDTE) font parties intégrantes de cette autorisation. Dans ce cadre, le DDTE a observé que les chevaux détenus dans les boxes projetés n'auraient accès qu'à un pâturage, mais non à une aire de sortie toutes saisons durant les périodes où ce terrain serait impraticable (p. ex. lors de fortes pluies); il a en conséquence exigé la réalisation de trois aires de sortie toutes saisons comme condition préalable à l'accueil d'équidés. Par ailleurs, constatant que A._ ne s'était pas conformé à l'ordre de remise en état du 2 juillet 2003 - confirmé en dernier lieu par le Tribunal administratif, le 9 février 2006 -, le département a une nouvelle fois exigé l'évacuation du matériel électrique présent dans la remise, dans un délai échéant le 31 mars 2014, sous la menace d'une exécution par substitution et des peines d'amende prévues par l'art. 292 du Code pénal suisse du 21 décembre 1937 (CP; RS 311.0); il a en outre ordonné la mention au registre foncier de l'interdiction d'un usage non agricole du bâtiment et de l'ordre d'évacuation. Le 1 er janvier 2014, le Conseil d'Etat de la République et canton de Neuchâtel a rejeté le recours formé par A._ contre la décision du DDTE. Le prénommé a interjeté recours contre le prononcé du Conseil d'Etat devant la Cour de droit public du Tribunal cantonal de la République et canton de Neuchâtel. Par arrêt du 30 mai 2016, la cour cantonale a rejeté le recours. Le Tribunal cantonal a tout d'abord confirmé la nécessité de réaliser trois aires de sortie toutes saisons, jugeant le seul pâturage insuffisant à assurer cette fonction en cas de conditions météorologiques défavorables. La cour cantonale a ensuite considéré que l'ordre d'évacuation de la remise et la menace d'une exécution par substitution ne pouvaient constituer des clauses accessoires au permis de construire portant sur l'agrandissement de l'étable, ces deux édifices - bien qu'implantés sur la même parcelle - ne présentant aucun lien direct; l'instance précédente a jugé qu'il s'agissait de mesures d'exécution de la décision du 2 juillet 2003, n'apportant matériellement aucune modification à la situation et partant non susceptibles de recours, ce qui aurait dû conduire le Conseil d'Etat à prononcer l'irrecevabilité des griefs soulevés à ce propos. C. Agissant par la voie du recours en matière de droit public, A._ demande au Tribunal fédéral d'annuler l'arrêt attaqué, la décision rendue le 1 er décembre 2014 par le Conseil d'Etat ainsi que la décision du DDTE. Il requiert également l'octroi de l'effet suspensif. Se référant aux motifs de son arrêt, le Tribunal cantonal renonce à formuler des observations et propose le rejet du recours. Le Service juridique du Département de la justice, de la sécurité et de la culture conclut aussi au rejet, de même que la Commune de La Chaux-de-Fonds. Egalement appelé à se déterminer, l'Office fédéral du développement territorial ARE adhère à l'arrêt attaqué, tout en soulignant qu'il devrait, selon lui, être possible de subordonner l'octroi d'une nouvelle autorisation de construire hors de la zone à bâtir au rétablissement préalable d'un état conforme au droit. Par ordonnance du 25 août 2016, le Président de la Ire Cour de droit public a admis la requête d'effet suspensif.