Par lettres des 23 novembre 1994 et 12 janvier 1995, le Conseil d'Etat a informé X. et Y. qu'il ne lui appartenait pas de prendre la décision demandée. La compétence de fixer le traitement salarial des maîtres du cycle d'orientation incombait en effet au législateur cantonal qui en avait fait usage en édictant un décret prévoyant expressément une distinction salariale selon que l'enseignant possédait ou non un titre universitaire.
X. et Y. ont recouru à l'encontre des deux lettres précitées auprès de la Cour de droit public du Tribunal cantonal du canton du Valais. Ils ont principalement conclu à leur annulation et au renvoi de l'affaire au Conseil d'Etat pour décision sur le fond.