Faits :
A.
Par décision du 15 mars 2016, l'Office de l'assurance-invalidité du canton de Neuchâtel (ci-après: l'office AI) a nié le droit de A._ à une rente d'invalidité. Il a constaté notamment que le certificat médical du 10 décembre 2015 produit à la suite du projet de décision du 4 décembre précédent ne faisait pas état d'une atteinte à la santé objectivée.
B.
L'assuré a recouru contre cette décision auprès de la Cour de droit public du Tribunal cantonal de la République et canton de Neuchâtel le 2 mai 2016, concluant à son annulation et au renvoi de la cause à l'office AI pour instruction complémentaire et nouvelle décision au sens des considérants. Se fondant sur l'appréciation de son Service médical régional (SMR; avis du 9 mai 2016), selon laquelle au vu du suivi psychiatrique instauré, il était nécessaire de demander un rapport médical au Centre B._, l'office AI a informé la juridiction cantonale qu'il annulait sa décision du 15 mars 2016 (observations sur le recours du 10 mai 2016). Il a précisé que dans la mesure où A._ avait omis d'annoncer, en temps opportun, le suivi psychiatrique dont il bénéficiait, il n'y avait pas lieu de mettre les frais judiciaires à sa charge ni d'allouer de dépens à l'assuré.
Par jugement du 24 juin 2016, le tribunal cantonal a ordonné le classement du recours et mis à charge de l'office AI un émolument de décision de 200 fr., des débours par 20 fr. ainsi qu'une indemnité de dépens de 1'694 fr. 85 à verser à A._.
C.
L'office AI interjette un recours en matière de droit public contre ce jugement dont il demande l'annulation "avec ou sans renvoi à l'instance précédente". Il requiert également que l'effet suspensif soit octroyé au recours.

Considérant en droit :
1.
1.1. Le recours en matière de droit public peut être formé pour violation du droit, tel qu'il est délimité par les art. 95 et 96 LTF. Le Tribunal fédéral applique le droit d'office (art. 106 al. 1 LTF), n'étant limité ni par les arguments de la partie recourante, ni par la motivation de l'autorité précédente. Par exception à ce principe, il ne peut entrer en matière sur la violation d'un droit constitutionnel ou sur une question relevant du droit cantonal ou intercantonal que si le grief a été invoqué et motivé de manière précise par la partie recourante (art. 106 al. 2 LTF). A cet égard, sauf exceptions non pertinentes en l'espèce (cf. art. 95 let. c à e LTF), les dispositions de droit cantonal ne peuvent pas être attaquées comme telles devant le Tribunal fédéral (art. 95 LTF a contrario). Il est néanmoins possible de faire valoir que l'application qui en a été faite viole le droit fédéral, par exemple la protection contre l'arbitraire au sens de l'art. 9 Cst. ou la garantie d'autres droits constitutionnels (<ref-ruling> consid. 2.2 p. 69 et les références).
1.2. Aux termes de l'art. 99 al. 1 LTF, aucun fait nouveau ni preuve nouvelle ne peut être présenté à moins de résulter de la décision de l'autorité précédente. En l'espèce, la réponse du Centre B._ à un courrier du recourant datée du 6 juin 2016, soit avant le prononcé du jugement entrepris, produite en instance fédérale ne peut pas être prise en considération. Le recourant n'expose pas en quoi cette pièce résulterait du jugement entrepris, alors que la question du suivi psychiatrique de l'assuré avait fait l'objet d'une discussion en procédure cantonale (cf. réponse du 10 mai 2016), ni pour quel motif il ne l'a pas déposée devant la juridiction cantonale.
2.
2.1. Au vu du recours et des ses conclusions, est seul litigieux le point de savoir si la juridiction cantonale était en droit de mettre les frais et dépens de l'intimé à la charge de l'office recourant, dès lors que la procédure était devenue sans objet.
2.2. La réglementation du principe juridique selon lequel les frais judiciaires sont répartis en fonction de l'issue du litige, soit du succès des parties au litige, relève exclusivement du droit cantonal pour la procédure de recours de première instance dans le domaine du droit des assurances sociales (arrêt 9C_672/2008 du 23 octobre 2008 consid. 5.2.1). Ni l'art. 69 al. 1 bis LAI, ni l'art. 61 LPGA ne prévoient une telle règle. En l'occurrence, la juridiction cantonale a appliqué l'art. 47 al. 1 de la loi neuchâteloise sur la procédure et la juridiction administrative (LPJA; RSN 152.130), selon lequel en principe et sous réserve des dispositions contraires du droit fédéral, la partie qui succombe est condamnée au paiement des frais de procédure. Selon la jurisprudence neuchâteloise, citée par la Cour de droit public (RJN 1988 p. 254), lorsque la procédure de recours devient sans objet par suite d'une modification de la décision attaquée, le recourant est considéré en principe comme ayant eu gain de cause.
En ce qui concerne les dépens, l'art. 61 let. g LPGA prévoit que le recourant qui obtient gain de cause a droit au remboursement de ses frais et dépens dans la mesure fixée par le tribunal; leur montant est déterminé sans égard à la valeur litigieuse d'après l'importance et la complexité du litige. Selon la jurisprudence constante, le Tribunal fédéral admet également un droit fédéral de la partie recourante à des dépens en cas de procédure cantonale de recours devenue sans objet, lorsque les chances de succès du recours avant l'événement mettant fin au litige le justifient (<ref-ruling> consid. 3.1 p. 115 et les références). L'issue probable du procès est avant tout déterminante (<ref-ruling> consid. 2a p. 374). Celui qui obtient gain de cause mais qui doit assumer lui-même la responsabilité d'un procès mené inutilement en raison de la violation de son obligation de collaborer n'a pas droit à des dépens (arrêt 9C_797/2015 du 3 décembre 2015 consid. 3 et les références).
3.
3.1. Le recourant fait tout d'abord grief à la juridiction cantonale d'avoir enfreint son obligation de motiver et violé son droit d'être entendu.
Le droit d'être entendu consacré à l'art. 29 al. 2 Cst. implique notamment l'obligation pour l'autorité - et le juge saisi d'un recours - de motiver sa décision, afin que ses destinataires et toutes les personnes intéressées puissent la comprendre, la contester utilement s'il y a lieu et que l'autorité de recours puisse exercer son contrôle. Il suffit cependant, selon la jurisprudence, que l'autorité de décision mentionne, au moins brièvement, les motifs qui l'ont guidée et sur lesquels elle a fondé sa décision; elle n'est pas tenue d'exposer et de discuter tous les faits, moyens de preuve et griefs invoqués par les parties. Il n'y a violation du droit d'être entendu que si l'autorité ne satisfait pas à son devoir minimum d'examiner et de traiter les problèmes pertinents (<ref-ruling> consid. 3.2.1 p. 564 s. et les références; cf. aussi <ref-ruling> consid. 1.3.1 p. 253 et les références).
3.2. En l'espèce, la décision entreprise mentionne les motifs concrets pour lesquels l'office recourant a été considéré comme la partie qui succombe et par conséquent été soumis au paiement des frais judiciaires et dépens de l'intimé. La juridiction cantonale a en effet constaté que dans les observations du 10 mai 2016 (réponse de l'administration au recours de l'assuré), le recourant avait reconnu que l'instruction de la cause était lacunaire sur le plan psychiatrique et annulé sa décision du 15 mars 2016. Dans ces circonstances, elle a expliqué que la procédure de recours était devenue sans objet et que l'assuré était alors considéré comme ayant eu gain de cause. Aussi, même si la juridiction cantonale ne s'est pas penchée en détail sur la réponse du 10 mai 2016, notamment sur le fait que l'instruction lacunaire n'aurait pas été imputable à l'office recourant mais à l'intimé, cela n'influe pas sur le fait que l'administration était à même de comprendre le jugement entrepris, soit les raisons pour lesquelles elle était considérée comme ayant succombé. La juridiction cantonale a expliqué que le certificat médical du 10 décembre 2015 produit par l'assuré déjà lors de la procédure administrative faisait à l'époque état d'une atteinte psychique pour laquelle le médecin traitant conseillait un suivi psychothérapeutique, ce qui aurait alors dû mener l'office recourant à compléter l'instruction. Vu ces explications, même si l'instance précédente n'a pas répondu à tous les arguments du recourant, celui-ci a été à même de comprendre puis de contester utilement le jugement cantonal. On ne saurait dès lors reprocher à la juridiction cantonale d'avoir violé le droit d'être entendu de l'office recourant.
4.
4.1. Le recourant reproche également à la juridiction cantonale d'avoir apprécié les preuves de manière arbitraire. Il conteste en particulier avoir procédé à une instruction lacunaire. Selon lui, la juridiction cantonale ne pouvait déduire du certificat médical du 10 décembre 2015 l'existence d'une atteinte notablement et durablement incapacitante sur le plan psychique.
4.2. Le grief d'arbitraire, qu'il soit examiné en relation avec l'application du droit cantonal de procédure - dût-il alors être considéré comme suffisamment motivé - ou du droit fédéral (supra consid. 2.2), est mal fondé. En effet, l'office recourant perd de vue que la question à laquelle devait répondre la juridiction cantonale, au regard de l'issue probable du recours cantonal, n'était pas celle de savoir s'il existait une atteinte incapacitante à la santé mais celle de savoir si une instruction complémentaire était nécessaire d'après les informations dont il disposait avant d'annuler sa décision du 15 mars 2016. A cet égard, comme l'a constaté la juridiction cantonale, l'assuré avait déjà en procédure administrative produit un certificat médical daté du 10 décembre 2015. Il ressortait de ce document qu'un suivi psychothérapeutique était recommandé. Dans son recours auprès du tribunal cantonal, l'intimé a mentionné qu'il souffrait notamment d'une dépression réactionnelle suffisamment sévère pour que des troubles du comportement apparaissent, qu'il bénéficiait désormais d'un suivi psychiatrique par le docteur C._ au Centre B._ et qu'il avait déjà été suivi au niveau psychologique lors des hospitalisations à U._, à V._ en septembre 2015 et à l'étranger à Noël de la même année (cf. recours cantonal p. 4). C'est donc sans arbitraire que la juridiction cantonale a constaté qu'une instruction complémentaire au niveau psychique aurait dû être mise en oeuvre par l'office recourant qui, par conséquent, devait être considéré comme ayant succombé. On ajoutera qu'on ne saurait reprocher à l'intimé de n'avoir pas collaboré avec le recourant puisque dès le prononcé de la décision du 15 mars 2016, il lui appartenait de s'adresser à la juridiction cantonale pour faire valoir tout élément utile, dont le début du suivi psychiatrique.
5.
Vu le sort du litige, la requête d'effet suspensif n'a plus d'objet.
6.
Les frais judiciaires sont mis à la charge du recourant qui succombe (art. 66 al. 1 première phrase LTF).

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est rejeté.
2.
Les frais judiciaires, arrêtés à 600 fr., sont mis à la charge du recourant.
3.
Le présent arrêt est communiqué aux parties, au Tribunal cantonal de la République et canton de Neuchâtel, Cour de droit public, et à l'Office fédéral des assurances sociales.
Lucerne, le 10 octobre 2016
Au nom de la IIe Cour de droit social
du Tribunal fédéral suisse
La Présidente : Glanzmann
La Greffière : Flury