Faits: Faits: A. Du 1er janvier 1998 au 31 décembre 2000, A._ a travaillé comme collaborateur à temps partiel, puis à plein temps, de X._ Sàrl, pour un salaire brut mensuel de 3'436 fr. 20. Le contrat de travail prévoyait une clause de prohibition de concurrence, contenant une peine conventionnelle maximale de 25'000 fr. pour chaque violation. Le 5 mars 2002, X._ Sàrl a déposé devant le Tribunal du travail du canton du Valais une demande tendant notamment au paiement de cette somme, au motif que son ancien employé exerçait une activité concurrente dans des magasins de jeux video. Le 22 octobre 2002, le Tribunal du travail a partiellement admis la demande et condamné A._ à payer 6'000 fr. avec intérêt à 5% dès le 5 mars 2002, étant précisé que ce dernier avait reconnu devoir 2'000 fr. de ce chef. Le 4 février 2003, ce dernier a appelé de ce jugement devant la Cour civile II du Tribunal cantonal du canton du Valais. Par jugement du 19 avril 2004, cette juridiction a prononcé l'irrecevabilité de l'appel. Elle a retenu que la valeur litigieuse de 4'000 fr, représentant la différence entre le montant combattu (6'000 fr.) et le montant reconnu (2'000 fr.), était inférieure à la limite prévue à l'art. 46 OJ, à laquelle se réfère l'art. 32c al. 1 de la loi cantonale sur le travail, du 16 novembre 1966 (ci-après: LCT). La Cour civile II a estimé que la valeur litigieuse régissant la recevabilité de l'appel devait être déterminée sur la base des prétentions contestées devant elle. Le 4 février 2003, ce dernier a appelé de ce jugement devant la Cour civile II du Tribunal cantonal du canton du Valais. Par jugement du 19 avril 2004, cette juridiction a prononcé l'irrecevabilité de l'appel. Elle a retenu que la valeur litigieuse de 4'000 fr, représentant la différence entre le montant combattu (6'000 fr.) et le montant reconnu (2'000 fr.), était inférieure à la limite prévue à l'art. 46 OJ, à laquelle se réfère l'art. 32c al. 1 de la loi cantonale sur le travail, du 16 novembre 1966 (ci-après: LCT). La Cour civile II a estimé que la valeur litigieuse régissant la recevabilité de l'appel devait être déterminée sur la base des prétentions contestées devant elle. B. A._ interjette un recours de droit public au Tribunal fédéral contre la décision du 19 avril 2004. Invoquant une violation arbitraire de l'art. 32c al. 1 LCT, et se rapportant au système de l'art. 46 OJ, qui a inspiré la disposition cantonale, A._ soutient que la valeur litigieuse doit se déterminer sur la base des prétentions contestées devant le Tribunal du travail. Ainsi, la valeur litigieuse est de 23'000 fr. (25'000. fr. moins 2'000. fr.), de sorte que le prononcé d'irrecevabilité est arbitraire. Il conclut à l'annulation de la décision attaquée. L'intimée n'a pas pris position sur le recours. Le Tribunal cantonal se réfère à ses considérants. 