Faits: Faits: A. A.a Par décision du 5 juillet 1996, l'Office AI du canton du Valais (ci-après : l'office AI) a rejeté la demande de prestations présentée le 29 mars 1995 par M._, né en 1957. Saisi d'un recours de l'assuré, le Tribunal cantonal valaisan des assurances a annulé cette décision et renvoyé la cause à l'administration pour un complément d'instruction médicale (jugement du 25 septembre 1997). Par arrêt du 28 juin 1998, le Tribunal fédéral des assurances a partiellement admis le recours de droit administratif interjeté par M._ et réformé le jugement entrepris au sens des considérants. L'office AI a repris l'instruction du dossier conformément aux injonctions reçues et rendu une nouvelle décision, le 14 novembre 2001, par laquelle il a derechef refusé à l'assuré le droit à des prestations. Cette décision, confirmée par jugement cantonal du 2 septembre 2002, est entrée en force. A.b Le 14 novembre 2002, M._, a déposé une nouvelle demande de prestations, invoquant une aggravation de son état de santé et demandant une rente à partir de juillet 2001. Plusieurs rapports médicaux ont été versés au dossier (notamment des docteurs B._, A._ et F._ du Centre hospitalier X._). Appelé à donner son avis sur le cas, le docteur T._, médecin-conseil de l'office AI, a préconisé la mise en oeuvre d'une expertise médicale. Par communication du 3 novembre 2003, l'office AI a informé l'assuré de la nécessité d'organiser une expertise pluridisciplinaire et indiqué qu'il serait convoqué à cette fin par le Centre d'observation médicale de l'AI (COMAI). Par lettre du 17 novembre suivant, M._ s'est opposé au principe d'une nouvelle mesure d'instruction médicale, faisant valoir que son état de santé était suffisamment élucidé. Par «décision incidente» du 28 novembre 2003, l'office AI a écarté les objections du prénommé et confirmé le mandat d'expertise au COMAI. Par «décision incidente» du 28 novembre 2003, l'office AI a écarté les objections du prénommé et confirmé le mandat d'expertise au COMAI. B. Par jugement du 24 mars 2004, le Tribunal cantonal valaisan des assurances a partiellement admis le recours formé par l'assuré contre cette dernière décision, annulé celle-ci et renvoyé la cause à l'office AI à charge pour lui d'en compléter l'instruction dans le sens des considérants. B. Par jugement du 24 mars 2004, le Tribunal cantonal valaisan des assurances a partiellement admis le recours formé par l'assuré contre cette dernière décision, annulé celle-ci et renvoyé la cause à l'office AI à charge pour lui d'en compléter l'instruction dans le sens des considérants. C. L'office AI interjette recours de droit administratif contre ce jugement, dont il requiert l'annulation. Il conclut à la confirmation de sa décision du 28 novembre 2003. Sous suite de dépens, M._ conclut, principalement, à l'irrecevabilité du recours et, subsidiairement, à son rejet. L'Office fédéral des assurances sociales a renoncé à se déterminer. 