Faits: Faits: A. A._, né en 1975, est arrivé en Suisse comme réfugié avec sa famille en 1986. Après avoir commencé un apprentissage en électronique qu'il n'a pas terminé, l'intéressé a travaillé en qualité de serveur puis de magasinier au service de M._ du 1er juillet 2000 au 30 juin 2003. Invoquant souffrir de dépression chronique depuis octobre 2002, il a déposé, le 23 juin 2003, une demande de rente d'invalidité. Après avoir pris connaissance d'une expertise psychiatrique (du docteur B._) de l'assuré ordonnée par l'assureur-maladie de ce dernier, le médecin-conseil de l'AI a considéré que l'assuré ne présentait pas de trouble psychique susceptible d'entraîner une incapacité de travail de longue durée. Par décision du 3 février 2004, confirmée sur opposition le 6 mai suivant, l'Office cantonal AI du Valais (ci-après: l'OAI) a refusé à l'assuré l'octroi d'une rente, motif pris que son taux d'invalidité était nul. Après avoir pris connaissance d'une expertise psychiatrique (du docteur B._) de l'assuré ordonnée par l'assureur-maladie de ce dernier, le médecin-conseil de l'AI a considéré que l'assuré ne présentait pas de trouble psychique susceptible d'entraîner une incapacité de travail de longue durée. Par décision du 3 février 2004, confirmée sur opposition le 6 mai suivant, l'Office cantonal AI du Valais (ci-après: l'OAI) a refusé à l'assuré l'octroi d'une rente, motif pris que son taux d'invalidité était nul. B. A._ a recouru contre cette décision devant le Tribunal cantonal des assurances en concluant, sous suite de dépens, principalement à son annulation et à ce qu'il fût mis au bénéfice d'une rente entière d'invalidité et, subsidiairement, à la mise en oeuvre d'une nouvelle expertise psychiatrique. Par jugement du 21 septembre 2004, le Tribunal cantonal des assurances a admis le recours, annulé la décision entreprise et renvoyé la cause à l'administration pour instruction complémentaire (complément d'expertise ou nouvelle expertise) et nouvelle décision dans le sens des considérants. B. A._ a recouru contre cette décision devant le Tribunal cantonal des assurances en concluant, sous suite de dépens, principalement à son annulation et à ce qu'il fût mis au bénéfice d'une rente entière d'invalidité et, subsidiairement, à la mise en oeuvre d'une nouvelle expertise psychiatrique. Par jugement du 21 septembre 2004, le Tribunal cantonal des assurances a admis le recours, annulé la décision entreprise et renvoyé la cause à l'administration pour instruction complémentaire (complément d'expertise ou nouvelle expertise) et nouvelle décision dans le sens des considérants. C. L'OAI interjette un recours de droit administratif contre ce jugement dont il demande l'annulation. L'intimé conclut au rejet du recours tandis que l'Office fédéral des assurances sociales (OFAS) propose son admission. 