Faits : A. A.a. Entre 2005 et 2009, le Service cantonal des contributions du canton du Valais (ci-après: le Service cantonal) a envoyé à X._ plusieurs décisions de taxation en matière d'impôts cantonaux et communaux et d'impôt fédéral direct pour les années 2004 à 2007. Ces décisions de taxation n'ont pas fait l'objet d'une réclamation. A.b. Le 3 novembre 2011, à la requête de la commune d'Evolène, l'Office des poursuites du district de Lausanne a notifié à X._ un commandement de payer concernant les impôts communaux relatifs aux années 2004 à 2007, contre lequel le contribuable a formé opposition. Le 20 février 2012, le Juge de paix du district de Lausanne a prononcé la mainlevée définitive de l'opposition (art. 105 al. 2 LTF). Le 28 septembre 2012 (recte: 26 septembre 2012), la Cour des poursuites et faillites du Tribunal cantonal du canton de Vaud a admis le recours formé par X._ contre la décision précitée et a maintenu l'opposition, au motif qu'il n'était pas établi que les factures des impôts en question avaient été notifiées au contribuable. A.c. Le 18 octobre 2013, la commune d'Evolène a notifié sous pli recommandé à X._ les bordereaux communaux pour les périodes 2004 à 2007. Par écriture du 30 octobre 2013, le contribuable a contesté formellement devoir les montants d'impôts réclamés. B. Par décision du 14 novembre 2014, le Service cantonal a déclaré irrecevable la réclamation du 30 octobre 2013 au motif qu'elle était tardive. Le 16 décembre 2014, X._ a recouru contre cette décision devant la Commission de recours en matière fiscale du canton du Valais (ci-après: la Commission de recours). Par décision du 27 mai 2015, la Commission de recours a admis le recours, annulé la décision d'irrecevabilité du 14 novembre 2014 et renvoyé l'affaire au Service cantonal pour qu'il entre en matière. La Commission de recours a retenu, en substance, que les autorités fiscales ne pouvaient établir la preuve d'une notification des bordereaux qu'à partir du 18 octobre 2013, de sorte que la réclamation formée le 30 octobre 2013 n'était pas tardive. C. Agissant par la voie du recours en matière de droit public, le Service cantonal demande au Tribunal fédéral, sous suite de frais, d'admettre le recours et de confirmer sa décision sur réclamation du 14 novembre 2014. Subsidiairement, il requiert le renvoi de la cause à la Commission de recours pour "nouvelle décision au sens du présent recours". Le contribuable et la Commission de recours concluent au rejet du recours. L'Administration fédérale des contributions propose l'admission du recours.