Faits: A. M._ s'est annoncé à l'Office cantonal genevois de l'assurance-invalidité (ci-après: office AI) et a obtenu une rente entière d'invalidité à compter du 1er mars 2005 (décisions des 4 février et 22 mai 2008). Dans le cadre d'une procédure de révision initiée d'office, l'administration a interrogé le prénommé sur sa situation médicale et financière (cf. procès-verbal du 18 septembre 2012). A la suite de cet entretien, elle a demandé à la Caisse fédérale de compensation de suspendre le versement de la rente d'invalidité de M._ avec effet immédiat (courrier du 12 octobre 2012). Le 9 novembre 2012, l'intéressé s'est enquis par téléphone auprès de l'office AI de l'absence de versement de sa rente d'invalidité. Celui-ci lui a répondu, par courrier du 12 novembre 2012, avoir suspendu la rente d'invalidité avec effet immédiat dès lors qu'il avait repris une activité lucrative sans l'en avertir. Il lui a indiqué qu'il était en droit de demander une décision formelle à ce sujet. Le 21 novembre 2012, l'assuré a contesté la suspension de sa rente d'invalidité et demandé la reprise immédiate de son versement. D'après lui, le courrier du 12 novembre 2012 avait valeur de décision. Le 4 décembre 2012, l'administration a pris acte qu'une décision formelle était requise. B. Le 7 décembre 2012, l'assuré a recouru auprès de la Chambre des assurances sociales de la Cour de Justice de la République et canton de Genève à l'encontre de la "décision" du 12 novembre 2012 en concluant principalement à sa nullité et, subsidiairement, à son annulation. Invité à se prononcer sur la recevabilité du recours, l'office AI a conclu à son irrecevabilité. Par jugement du 4 février 2013, la Cour de Justice a admis le recours, annulé la "décision" du 12 novembre 2012 et ordonné la reprise du versement de la rente d'invalidité depuis le jour de sa suspension. C. L'office AI interjette un recours en matière de droit public contre ce jugement dont il demande l'annulation "en ce qu'il déclare recevable le recours" de M._ et ordonne à l'administration de reprendre le versement de la rente d'invalidité depuis le jour de sa suspension. Préalablement, il a requis l'octroi de l'effet suspensif à son recours. M._ conclut à titre préjudiciel au rejet de la requête d'effet suspensif. Sur le fond, il conclut principalement à l'irrecevabilité du recours et subsidiairement à son rejet, le tout sous suite de frais et dépens. L'Office fédéral des assurances sociales a renoncé à se déterminer. 