Faits : A. A.a. A._ a déposé une demande de prestations (mesures médicales) auprès de l'Office AI du canton de Neuchâtel (ci-après l'office AI) le 9 avril 1997, en indiquant souffrir de naevi dès la naissance. L'office AI a pris des renseignements auprès du docteur B._, spécialiste en dermatologie et vénéréologie. Ce dernier a diagnostiqué une infirmité congénitale, à savoir des naevi multiples de grande taille, qui exposaient à trois types de complications: des problèmes esthétiques, un risque accru de mélanome et une éventuelle mélanose neuro-cutanée. Il a préconisé une surveillance clinique régulière, soit des examens de contrôle effectués chaque fois à un an d'intervalle, et un examen ophtalmologique ainsi qu'une résonance magnétique nucléaire à la recherche d'une éventuelle hyperplasie mélanocytaire intra-cérébrale (rapports des 8 mars et 24 avril 1997). Par décision du 16 septembre 1997, l'administration a rejeté la demande de l'intéressé. Elle a considéré que le traitement relatif à l'infirmité congénitale dont souffrait A._ n'incombait pas à l'assurance-invalidité dans la mesure où les conditions fixées par le ch. 109 de l'annexe à l'ordonnance du 9 décembre 1985 concernant les infirmités congénitales n'étaient pas réunies (ci-après: OIC, RS 831.232.21; dégénérescence maligne ou excision simple impossible en raison de la grandeur ou de la localisation de l'infirmité). A.b. L'intéressé a présenté une nouvelle demande le 29 novembre 2012. Il soutenait que, selon les derniers avis médicaux, il était inadmissible que son cas n'ait pas été pris en charge par l'assurance-invalidité dès la première demande et que les risques liés aux naevi congénitaux étaient importants. L'office AI a requis des informations auprès du docteur B._. Le médecin a confirmé le diagnostic retenu dans son rapport précédent et précisé qu'il s'agissait d'une infirmité congénitale au sens de l'OIC (rapport du 28 décembre 2012). Se fondant sur l'appréciation du Service médical régional (SMR; avis du 6 juin 2013), l'administration a fait part à A._ de son intention de rejeter la demande (projet de décision du 21 juin 2013). L'intéressé s'y est opposé et a produit un rapport du docteur B._ daté du 17 août 2013. L'office AI a à nouveau demandé l'avis du SMR, qui est revenu sur sa position en mentionnant que vu le nombre et la grandeur de certains naevi, toute excision était impossible et par conséquent, les mesures médicales devaient être prises en charge (rapport du 10 octobre 2013). L'administration a malgré tout rejeté la demande au motif que la situation n'avait pas changé depuis 1997, que l'assurance devait prendre en charge une excision compliquée en raison de la grandeur ou de la localisation et qu'en l'occurrence il n'était pas question d'excision (décision du 7 avril 2015). B. Par jugement du 5 avril 2016, le Tribunal cantonal de la République et canton de Neuchâtel, Cour de droit public, a admis le recours formé par A._, annulé la décision administrative et renvoyé la cause à l'intimé pour nouvelle décision au sens des considérants. C. L'office AI interjette un recours en matière de droit public contre ce jugement dont il demande l'annulation. L'intéressé propose le rejet du recours, tandis que l'Office fédéral des assurances sociales a renoncé à se déterminer.