Faits: A. R._, né en 1954, a été engagé par X._, en qualité d'auxiliaire, au poste de responsable de la communication pour une durée déterminée (du 15 février 2001 au 31 décembre 2001). Son engagement a été reconduit jusqu'au 31 décembre 2002. Le 7 janvier 2003, le Conseil d'Etat l'a mis au bénéfice d'un engagement de durée indéterminée. Le 9 avril 2008, l'intéressé a été nommé fonctionnaire avec effet au 1er janvier 2008 pour la période administrative en cours. R._ a été incapable de travailler pour cause de maladie à partir du 14 février 2011. Il n'a plus repris le travail. Par décision du 28 septembre 2011, le Conseil d'Etat a résilié ses rapports de service. Cette décision faisait notamment référence à un rapport du 22 août 2011 dans lequel S._, supérieur hiérarchique de l'intéressé, indiquait que celui-ci n'avait pas rempli les objectifs qui lui avaient été assignés le 15 décembre 2010. Le 19 octobre 2011, le Conseil d'Etat a rendu une deuxième décision, annulant et remplaçant celle du 28 septembre 2011 et reportant au 31 janvier 2012 la date de cessation des rapports de service. Le Conseil d'Etat a retiré l'effet suspensif à un recours éventuel. B. R._ a successivement recouru contre ces décisions devant la Cour de droit public du Tribunal cantonal du canton du Valais. La juridiction cantonale a joint les causes. Le 15 décembre 2011, elle a restitué l'effet suspensif aux recours. Statuant au fond le 12 avril 2012, elle a déclaré irrecevable le recours contre la décision du 28 septembre 2011, au motif qu'il était sans objet (cause A1 11 228). Elle a admis le recours en tant qu'il était dirigé contre la décision du 19 octobre 2011, qu'elle a réformée en ce sens que la résiliation prononcée par le Conseil d'Etat prendrait effet au 14 mai 2012 (cause A1 11 255). C. L'Etat du Valais exerce un recours en matière de droit public par lequel il conclut, principalement, à l'annulation de l'arrêt cantonal et à la confirmation de la décision du Conseil d'Etat du 19 octobre 2011. Subsidiairement, il conclut à l'annulation de l'arrêt attaqué et au renvoi de la cause à l'autorité précédente pour nouvelle décision au sens des motifs, le tout sous suite de frais et dépens. R._ conclut au rejet du recours et à la confirmation du jugement cantonal, sous suite de frais et dépens. Le tribunal cantonal met en doute la recevabilité du recours. Sur le fond, il conclut à son rejet.