Faits : A. A.X._, ressortissant de l'ex-Serbie-et-Montenegro né en 1976, est entré en Suisse en 1995, où il a déposé une demande d'asile. Il a été attribué au canton du Valais. A la suite de son mariage en 1997 avec une ressortissante suisse, A.X._ a obtenu, dans ce canton, une autorisation annuelle de séjour puis, en 2004, une autorisation d'établissement. Le divorce du couple a été prononcé le 16 janvier 2009. Le 26 octobre 2009, A.X._ s'est annoncé au contrôle des habitants de E._, dans le canton de Vaud. Remarié au Kosovo le 24 août 2009 avec une ressortissante kosovare dont il a divorcé en novembre 2010, A.X._ a entretenu à compter d'une date non indiquée dans l'arrêt cantonal une relation avec B._, ressortissante kosovare en séjour illégal en Suisse et dont le renvoi avait été ordonné en août 2011. Le couple a eu une fille, C.X._, née en 2011, de sorte que le délai de départ de B._ a été prolon gé au 31 octobre 2011. Celle-ci est toutefois restée en Suisse depuis cette date et a épousé A.X._ en avril 2012. Une seconde fille, D.X._, est née en 2013. Aucun titre de séjour ne leur a été délivré. Sur le plan professionnel, A.X._ a alterné des périodes d'emploi et de chômage. Depuis le 1 er avril 2010, il est au bénéfice d'un contrat de travail à durée indéterminée auprès d'une entreprise active dans la construction. Au 5 juin 2015, A.X._ faisait l'objet de poursuites pour un montant de 2'395 fr. et d'actes de défaut de biens pour un montant de 115'893 fr. B. Sur le plan pénal, A.X._ a fait l'objet de quatre condamnations entre 2000 et 2005, pour vols (peine de trente jours d'emprisonnement, avec sursis durant deux ans), vol d'importance mineure (peine de cinq jours d'arrêts avec sursis durant un an), menaces (peine ferme de dix jours d'emprisonnement) et escroquerie (peine ferme de vingt jours d'emprisonnement). Le Ministère public du canton de Zurich l'a condamné, le 30 janvier 2008, à une amende de 100 fr., convertie par la suite en une peine privative de liberté de substitution d'un jour, pour défaut de titre de transport. En raison de ces infractions, trois avertissements administratifs ont été signifiés à A.X._, en dates des 6 septembre 2000, 2 janvier 2001 et 18 décembre 2006. Par jugement du 5 octobre 2011 rendu sur appel, le Tribunal cantonal du Valais a reconnu A.X._ coupable de tentative de viol, de contrainte sexuelle et d'actes d'ordre sexuel avec des enfants pour avoir, le 30 septembre 2007, tenté de pénétrer de force une adolescente âgée de quinze ans et l'avoir obligée à accomplir des actes d'ordre sexuel. Il l'a condamné à une peine privative de liberté de trente mois avec sursis partiel de dix-huit mois et délai d'épreuve de quatre ans. Ce jugement a été confirmé par le Tribunal fédéral le 17 janvier 2012, qui a rejeté tant le recours déposé par le Ministère public, relatif à la fixation de la peine et à l'octroi du sursis partiel, que celui formé par A.X._, concernant la réalisation de l'infraction de contrainte sexuelle (arrêts 6B_717/2011 et 6B 729/2011; cf. art 105 al. 2 LTF). Le premier arrêt met notamment en évidence l'absence de remords et de prise de conscience de l'intéressé en relation avec les actes commis, ainsi que sa propension à nier les faits. A.X._ a exécuté entre les 30 juillet 2012 et 26 juin 2013 la peine résultant du jugement du 5 octobre 2011, sous le régime de la semi-détention. C. Le 2 avril 2013, le Service de la population du canton de Vaud a refusé d'accorder à A.X._ le droit de s'établir dans le canton de Vaud, comme celui-ci en avait formulé la demande le 3 novembre 2009, ainsi que de délivrer des autorisations de séjour à son épouse et leur enfant. Le recours tendant à l'annulation de cette décision a été rejeté le 22 octobre 2013 par la Cour de droit administratif et public du Tribunal cantonal vaudois. Par arrêt 2C_1103/2013 du 26 juillet 2014, le Tribunal fédéral a jugé irrecevable le recours en matière de droit public formé contre cet arrêt et rejeté le recours constitutionnel subsidiaire. Le 15 septembre 2014, A.X._, son épouse et leurs enfants ont sollicité le réexamen de la décision du 2 avril 2013. Le Service de la population du canton de Vaud a déclaré irrecevable, subsidiairement a rejeté cette demande par décision du 15 octobre 2014, laquelle a été confirmée par arrêt du 6 janvier 2015 de la Cour de droit administratif et public du Tribunal cantonal vaudois. Par arrêt 2C_132/2015 du 20 février 2015, le Tribunal fédéral a jugé irrecevable le recours en matière de droit public et rejeté dans la mesure de sa recevabilité le recours constitutionnel subsidiaire formé contre l'arrêt cantonal. Le 30 mars 2015, le Service de la population du canton de Vaud a imparti à B.X._, C.X._ et D.X._ un délai échéant le 30 avril 2015 pour quitter le territoire helvétique. D. Le 18 mai 2015, le Service de la population et des migrations du canton du Valais (ci-après: le Service cantonal) a informé A.X._ qu'il envisageait de révoquer son autorisation d'établissement et de prononcer son renvoi de Suisse compte tenu des condamnations pénales et des trois sérieux avertissements administratifs dont il avait fait l'objet. Dans ses observations du 4 juin 2015, A.X._ a demandé que son autorisation d'établissement soit maintenue. Dans la même écriture, B.X._, C.X._ et D.X._ ont sollicité le bénéfice du regroupement familial. Par décision du 8 juin 2015, le Service cantonal a révoqué l'autorisation d'établissement de A.X._ et prononcé son renvoi de Suisse. Le Conseil d'Etat du canton du Valais (ci-après: le Conseil d'Etat) a, le 11 novembre 2015, rejeté le recours de A.X._ et déclaré irrecevable celui formé par B.X._, C.X._ et D.X._ contre cette décision. Par arrêt du 15 avril 2016, la Cour de droit public du Tribunal cantonal du canton du Valais (ci-après: le Tribunal cantonal) a rejeté le recours de A.X._ contre ce dernier prononcé et déclaré irrecevable celui de B.X._, C.X._ et D.X._, faute de qualité pour recourir. E. Agissant par la voie du recours en matière de droit public et celle, subsidiaire, du recours constitutionnel, A.X._, ainsi que B.X._, C.X._ et D.X._ concluent, sous suite de frais et dépens, à l'annulation de l'arrêt du Tribunal cantonal du 15 avril 2016 et à ce qu'un titre de séjour soit délivré à chacun d'entre eux. Le Tribunal cantonal renonce à se déterminer. Le Conseil d'Etat conclut au rejet du recours et indique que le Service cantonal a renoncé à présenter des observations. Le Secrétariat d'Etat aux migrations n'a pas déposé d'observations sur le recours dans le délai imparti à cet effet. F. Par ordonnance du 23 mai 2016, le Président de la IIe Cour de droit public du Tribunal fédéral a admis la demande d'effet suspensif contenue dans le recours.