Faits: A. A.a. A._, né en 1950, a travaillé depuis de nombreuses années en qualité d'employé au service de différents offices des poursuites et faillites (OPF) du canton du Valais. Le 9 septembre 2003, le Conseil d'Etat du canton du Valais l'a nommé au poste de préposé à l'OPF de B._. Sa rémunération a été fixée selon la classe 6 de l'échelle des traitements des employés de l'Etat du Valais, moyennant une année d'attente en classe 7. A.b. Le 18 janvier 2012, le Conseil d'Etat a introduit une nouvelle chaine de fonction en ce qui concerne le poste de préposé d'un OPF au sein de l'administration cantonale. Pour l'OPF de B._, cette chaine de fonction est la suivante: Classe 7 A l'engagement pour le titulaire d'un titre de formation supérieure de niveau master ou du brevet fédéral d'expert en matière de droit des poursuites pour dettes ou formation jugée équivalente. Classe 6 Après 3 années d'expérience dans la fonction de préposé d'un office des poursuites et faillites. Classe 5 Pour le titulaire qui dispose: - soit d'un titre de formation supérieure de niveau master et du brevet fédéral d'expert en matière de droit des poursuites pour dettes ou formation jugée équivalente et après 2 années en classe 6, - soit d'une formation jugée équivalente et 10 années d'expérience dans la fonction de préposé d'un office des poursuites et faillites. Chaque situation individuelle a été examinée à l'aune de ces nouveaux critères et des décisions ont été rendues dans les cas impliquant un changement de classe salariale. Les préposés ont été informés à ce sujet lors d'une séance de direction qui s'est tenue le 8 mars 2012. A.c. Le poste de A._, dont la rémunération avait été fixée sur la base de la classe 6, n'a pas fait l'objet d'une décision de changement de classe. Aussi, s'est-il adressé au délégué aux OPF en faisant valoir qu'il satisfaisait aux exigences de formation et d'expérience pour bénéficier d'un changement de classe. A l'appui de ses allégations, il a déposé la copie d'un certificat propédeutique délivré le 27 octobre 1971 par l'Institut des sciences de l'éducation, section de psychologie, de l'Université de C._. Après un échange de correspondance, le Conseil d'Etat a rendu une décision, le 14 novembre 2012, par laquelle il a rejeté la demande de A._ et confirmé le classement de son poste de préposé de l'OPF dans la classe 6 de l'échelle des traitements des employés de l'Etat du Valais. B. Saisie d'un recours contre cette décision, la Cour de droit public du Tribunal cantonal du Valais l'a rejeté par jugement du 19 juin 2013. C. A._ forme un recours en matière de droit public contre ce jugement dont il demande la réformation en ce sens que sa requête tendant à ce que son poste soit colloqué dans la classe 5 de l'échelle des traitements est admise. Subsidiairement, il conclut au renvoi de la cause à la cour cantonale pour nouveau jugement au sens des considérants, le tout sous suite de frais et dépens. Le Conseil d'Etat conclut au rejet du recours, tandis que la juridiction cantonale a renoncé à se déterminer. 