Faits :
A.
A.a. A._, né en 1958, nettoyeur, a été victime d'un accident de la circulation routière le 19 avril 1992 au cours duquel il a subi une fracture des pédicules de la vertèbre cervicale C2, sans lésions neurologiques. Par décision du 23 décembre 1993, l'Office de l'assurance-invalidité du canton de Genève (ci-après: l'office AI) a rejeté la demande de prestations déposée par l'assuré en date du 2 mars 1993. En substance, l'administration a retenu que l'assuré pouvait exercer une activité adaptée à ses limitations physiques à plein temps. Non contestée, cette décision est entrée en force.
A._ a ensuite alterné des périodes de chômage avec des emplois de courte durée, puis débuté une nouvelle activité professionnelle dans le domaine du jardinage et de la maçonnerie dès juin 1998.
A.b. En arrêt de travail depuis le 19 décembre 2000, A._ a présenté une nouvelle demande de prestations le 12 juin 2001. Après avoir recueilli l'avis des médecins traitants, l'office AI a confié la mise en oeuvre d'un examen bidisciplinaire aux docteurs B._, spécialiste en rhumatologie, et C._, spécialiste en psychiatrie et psychothérapie. Les médecins ont diagnostiqué - avec effet sur la capacité de travail - des cervicalgies chroniques post fracture des pédicules de C2 (du 19 avril 1992) et des lombalgies chroniques depuis mai 2000; l'assuré disposait d'une capacité de travail de 80 % dans son activité habituelle de nettoyeur ou toute autre activité adaptée. Il ne présentait en revanche aucun trouble psychique qui pouvait altérer sa capacité d'adaptation ou de limitations de la capacité de travail sur les plans psychique et mental (rapport du 27 décembre 2004).
L'assuré a déposé en cours de procédure une nouvelle demande de prestations le 21 mai 2007 et produit des avis médicaux faisant état d'une péjoration de son état de santé sur le plan somatique. Dans un rapport rédigé le 29 février 2008, la doctoresse D._, médecin auprès du Service médical régional de l'assurance-invalidité (SMR), a diagnostiqué - avec effet sur la capacité de travail - des cervicalgies droites dans le cadre d'une hernie discale C3-C4 non compressive et un status post fracture C2 (en 1992) sans séquelles neurologiques, des lombosciatalgies chroniques non déficitaires dans le cadre d'un trouble statique et dégénératif avec une insuffisance posturale et un status post neurolyse du nerf cubital du coude et du nerf médian au poignet gauche (2005), avec trouble sensitif et faiblesse résiduelle; l'assuré présentait une capacité de travail de 75 % dans une activité adaptée.
Par décision du 26 janvier 2009, l'office AI a tout d'abord refusé la mise en oeuvre de mesures d'ordre professionnel au motif qu'elles étaient vouées à l'échec et heurtaient manifestement le principe de la proportionnalité. Non contestée, cette décision est entrée en force. Se fondant sur les conclusions des rapports du 27 décembre 2004 et du 29 février 2008, l'office AI a ensuite nié le droit de l'assuré à une rente d'invalidité (décision du 25 février 2010). En bref, l'administration a considéré que l'assuré pouvait exercer une activité adaptée - à 80 % dès le 1er décembre 2000, puis à 75 % dès le 1er juillet 2007 - et réaliser ainsi un revenu excluant le droit à une rente d'invalidité.
B.
A._ a déféré la décision du 25 février 2010 à la Cour de justice de la République et canton de Genève, Chambre des assurances sociales. La juridiction cantonale a tout d'abord mis en oeuvre une expertise pluridisciplinaire auprès de l'Hôpital E._. Les docteurs F._, spécialiste en rhumatologie, G._, spécialiste en neurologie, H._, spécialiste en neurologie, et I._, spécialiste en cardiologie, ont indiqué que l'assuré présentait sur le plan somatique une capacité de travail entière dans une activité adaptée (rapport du 19 juillet 2012). Après la mise en oeuvre d'examens complémentaires, le docteur F._ a confirmé que l'assuré présentait - d'un point de vue rhumatologique - une capacité de travail de 100 % dans une activité sédentaire adaptée (rapport complémentaire du 13 novembre 2013). La cour cantonale a ensuite confié la réalisation d'une expertise psychiatrique au docteur K._, spécialiste en psychiatrie et psychothérapie. S'étant adjoint les services d'un neuropsychologue, le psychiatre a diagnostiqué un épisode dépressif majeur, isolé, en rémission partielle, un trouble douloureux (associé à des facteurs psychologiques et à des affections médicales), un trouble de conversion avec présentation mixte et une dépendance aux anxiolytiques; le médecin a également fait état notamment d'un fonctionnement intellectuel limite et d'un trouble de la personnalité non-spécifié, décompensé (personnalité fruste à traits abandonniques). L'assuré disposait d'un point de vue psychiatrique d'une capacité de travail de 30 % dans une activité adaptée après réadaptation, voire de 50 % dans un atelier protégé; déjà depuis 2002 il était "incapable d'actualiser une capacité de travail quelconque sans une aide extérieure spécialisée" (rapport du 6 juillet 2015, p. 42 et p. 50). L'office AI s'est déterminé sur les conclusions de l'expertise judiciaire en produisant un nouvel avis de son SMR (du 19 août 2015), tandis que l'assuré a remis l'avis de la doctoresse J._, psychiatre traitant (du 15 octobre 2015). Par jugement du 10 mars 2016, la Cour de justice a partiellement admis le recours, annulé la décision du 25 février 2010 et octroyé à l'assuré une rente entière d'invalidité dès le 1er janvier 2003. Elle a pour le surplus renvoyé la cause à l'office AI pour le calcul des prestations dues.
C.
L'office AI forme un recours en matière de droit public contre ce jugement dont il demande l'annulation. Il conclut principalement à la confirmation de la décision du 25 février 2010 ou, à ce défaut, au renvoi de la cause à l'autorité précédente pour qu'elle ordonne la réalisation d'une nouvelle expertise psychiatrique. En tout état de cause, il demande au Tribunal fédéral de constater que la rente ne peut en aucun cas remonter à une date antérieure au 26 janvier 2009.
L'intimé conclut au rejet du recours, tandis que l'Office fédéral des assurances sociales (OFAS) conclut à son admission.

Considérant en droit :
1.
Bien que le dispositif du jugement entrepris renvoie la cause à l'office recourant, il ne s'agit pas d'une décision incidente au sens de l'<ref-law>, car l'autorité précédente a statué définitivement sur les points contestés, le renvoi de la cause ne visant que le calcul de la rente entière de l'assurance-invalidité allouée. Le recours est dès lors recevable puisqu'il est dirigé contre un jugement final (<ref-law>; <ref-ruling> consid. 1.3 p. 127).
2.
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 (<ref-law>), n'étant limité ni par les arguments de la partie recourante, ni par la motivation de l'autorité précédente. Le Tribunal fédéral n'examine en principe que les griefs invoqués, compte tenu de l'exigence de motivation prévue à l'<ref-law>, et ne peut aller au-delà des conclusions des parties (<ref-law>). Il fonde son raisonnement sur les faits retenus par l'autorité précédente (<ref-law>) sauf s'ils ont été établis de façon manifestement inexacte ou en violation du droit au sens de l'<ref-law> (<ref-law>). La partie recourante qui entend s'écarter des faits constatés doit expliquer de manière circonstanciée en quoi les conditions de l'<ref-law> sont réalisées, sinon un état de fait divergent ne peut être pris en considération (<ref-law>).
3.
3.1. Est litigieux le droit de l'intimé à une rente d'invalidité dans le cadre d'une nouvelle demande de prestations présentée le 12 juin 2001. Selon les constatations de la juridiction cantonale, l'intimé a déposé à cette date une demande, tendant à l'octroi de mesures d'ordre professionnel, et une nouvelle demande de prestations le 21 mai 2007, tendant à l'octroi d'une rente d'invalidité. Contrairement à ce que prétend l'office AI, la demande de prestations du 12 juin 2001 avait déjà préservé le droit éventuel de l'assuré à une rente d'invalidité. Selon la jurisprudence, une demande comprend en effet toutes les prétentions de l'assurance-invalidité qui, de bonne foi, sont liées à la survenance du risque annoncé (<ref-ruling> consid. 2 p. 196; arrêt 9C_92/2008 du 24 novembre 2008 consid. 3.2). L'office recourant a du reste expressément examiné le droit de l'intimé à une rente d'invalidité depuis le 19 décembre 2000, date correspondant au début du délai d'attente (décision du 25 février 2010). L'office recourant ne saurait dès lors être suivi lorsqu'il affirme que le début du droit à la rente de l'intimé remontait au plus tôt à la date de la décision du 26 janvier 2009.
3.2. Le jugement entrepris expose les dispositions légales applicables au litige dans leur teneur en vigueur à partir du 1er janvier 2012, sans tenir compte des versions antérieures de la LAI, notamment celle applicable avant l'entrée en vigueur, au 1er janvier 2003, de la LPGA. Le fait que les premiers juges ont rappelé et appliqué exclusivement le droit en vigueur à partir du 1er janvier 2012 - alors que le droit litigieux devait être examiné à partir de la nouvelle demande (du 12 juin 2001) - reste sans incidence sur le sort de la procédure car les normes de la LPGA sur l'incapacité de gain (art. 7), l'invalidité (art. 8) et l'évaluation de l'invalidité (art. 16) correspondent aux notions précédemment en vigueur (<ref-ruling>). Il suffit de renvoyer au jugement entrepris sur ces différents points.
4.
4.1. La juridiction cantonale a octroyé à l'intimé une rente entière d'invalidité dès le 1er janvier 2003. En se fondant sur les conclusions du rapport pluridisciplinaire (du 19 juillet 2012), elle a tout d'abord constaté l'absence de troubles organiques évidents. En se ralliant aux conclusions de l'expertise psychiatrique (rapport du 6 juillet 2015), les premiers juges ont ensuite retenu que l'intimé avait développé progressivement un trouble somatoforme douloureux depuis 2002, qui était devenu plus prononcé à partir de 2009-2010, un trouble de conversion et un trouble de la personnalité non-spécifié décompensé. Ils ont également fait état d'un tableau dysthymique remontant "en tout cas à 2002, début de la période d'inactivité," et qui s'était aggravé de manière significative au décès de la mère de l'assuré (en septembre 2013). Aussi, selon la juridiction cantonale, l'intimé était incapable d'actualiser une quelconque capacité de travail sans une aide spécialisée - qui lui a été refusée par l'office AI (décision du 26 janvier 2009) - depuis 2002 et présentait un trouble somatoforme douloureux invalidant à 100 %.
4.2. L'office recourant reproche aux premiers juges d'avoir procédé à une appréciation arbitraire des preuves et violé le principe de la libre appréciation des preuves en suivant les conclusions de l'expertise psychiatrique judiciaire (du 6 juillet 2015). Il soutient que le rapport du docteur K._ présente de nombreuses erreurs, omissions et contradictions. Qui plus est, le médecin a superposé aux déclarations de l'intimé des hypothèses "étiopathogéniques" qui n'avaient nullement été évoquées par les précédents médecins.
5.
5.1.
5.1.1. En principe, le juge ne s'écarte pas sans motifs impératifs des conclusions d'une expertise médicale judiciaire, la tâche de l'expert étant précisément de mettre ses connaissances spéciales à la disposition de la justice afin de l'éclairer sur les aspects médicaux d'un état de fait donné (<ref-ruling> consid. 4.4 p. 469 et la référence). Selon la jurisprudence, peut constituer une raison de s'écarter d'une expertise judiciaire le fait que celle-ci contient des contradictions, ou qu'une surexpertise ordonnée par le tribunal en infirme les conclusions de manière convaincante. En outre, lorsque d'autres spécialistes émettent des opinions contraires aptes à mettre sérieusement en doute la pertinence des déductions de l'expert, on ne peut exclure, selon les cas, une interprétation divergente des conclusions de ce dernier par le juge ou, au besoin, une instruction complémentaire sous la forme d'une nouvelle expertise médicale (<ref-ruling> consid. 3b/aa et les références).
5.1.2. Lorsque, comme en l'occurrence, l'autorité de recours juge l'expertise judiciaire concluante et en fait sien le résultat, le Tribunal fédéral n'admet le grief d'appréciation arbitraire que si l'expert n'a pas répondu aux questions posées, si ses conclusions sont contradictoires ou si, d'une quelconque autre façon, l'expertise est entachée de défauts à ce point évidents et reconnaissables, même sans connaissances spécifiques, que le juge ne pouvait tout simplement pas les ignorer. Il n'appartient en particulier pas au Tribunal fédéral de vérifier si toutes les affirmations de l'expert sont exemptes d'arbitraire; sa tâche se limite bien plutôt à examiner si l'autorité intimée pouvait, sans arbitraire, se rallier au résultat de l'expertise (arrêt 9C_323/2015 du 25 janvier 2016 consid. 5.1 et les références).
5.2. Le grief tiré d'une violation du principe de la libre appréciation des preuves (art. 61 let. c LPGA) et du devoir qui en découle de procéder à une appréciation complète, rigoureuse et objective des rapports médicaux, en relation avec leur contenu, est une question de droit, qui est soumise au libre examen du Tribunal fédéral (<ref-ruling> consid. 4.1 p. 400).
6.
6.1. Après avoir rappelé que le docteur K._ a exprimé sa difficulté à reconstituer a posteriori l'évolution de l'état de santé d'un assuré qui connaissait d'importantes difficultés à expliquer son état psychique, les premiers juges ont tout d'abord retenu que l'expert concluait à l'existence d'un tableau dysthymique depuis au moins 2002. Ils ne se sont toutefois pas exprimés sur l'impact de ce tableau dysthymique sur la capacité de travail de l'intimé, étant rappelé que, selon la jurisprudence, un tel trouble ne représente pas à lui seul une atteinte à la santé invalidante (p. ex. arrêt 9C_146/2015 du 19 janvier 2016 consid. 3.2 et les références). On ajoutera que l'expert a noté que l'assuré ne présentait probablement pas encore une pathologie thymique significative au moment de l'examen clinique (du 18 novembre 2004) effectué par la doctoresse C._. La psychiatre avait en effet considéré que l'intimé ne présentait "aucune plainte" (rapport du 27 décembre 2004).
Au regard des constatations du docteur K._, il n'est par ailleurs pas possible de retenir une affection de la lignée dépressive suffisamment sévère pour limiter la capacité de travail de l'intimé jusqu'à la date déterminante de la décision litigieuse (du 25 février 2010). L'expert a en particulier relevé que l'assuré présentait un trouble dépressif majeur entraînant une incapacité de travail totale "au moins" depuis septembre 2013 (décès de la mère de l'assuré), même s'il était très probable que cette incapacité de travail fut antérieure; selon l'expert, c'était "peut-être" en mai 2012 que l'atteinte thymique a occupé une place plus significative. L'assuré avait en outre été déstabilisé par l'opération d'un ou plusieurs diverticules intestinaux en 2011, qui lui avait rappelé les circonstances du décès de son père. En tout état de cause et sans qu'il soit nécessaire de se prononcer plus avant à ce sujet, la péjoration du tableau dysthymique de l'intimé est donc postérieure à la diverticulose colique opérée en mai 2011. Cet élément de fait, postérieur à la décision administrative du 25 février 2010, sort de l'objet de la contestation. Selon la jurisprudence constante, il incombe au juge d'apprécier la légalité des décisions attaquées, sous réserve d'exceptions non réalisées en l'espèce, d'après l'état de fait existant au moment où la décision administrative a été rendue (cf. <ref-ruling> consid. 3.1.1 p. 220; <ref-ruling> consid. 1b p. 366). Il n'y avait dès lors pas lieu de tenir compte de la phase dépressive liée notamment à un processus de deuil et qui est intervenue postérieurement au prononcé administratif.
6.2. Il en va de même du trouble somatoforme douloureux et des effets incapacitants diagnostiqués par le docteur K._.
A cet égard, le médecin a indiqué qu'il était "possible" que le trouble somatoforme douloureux se fût développé progressivement à partir de 2002 et qu'il fût devenu plus prononcé "probablement" à partir de 2009-2010 (apparition de troubles dans l'hémicorps droit en lien avec l'aggravation de l'état de santé de la mère de l'intimé). Il a toutefois échappé aux premiers juges que le psychiatre s'est écarté à cette occasion du mandat d'expertise pour inscrire la perception subjective que l'assuré se faisait de sa situation de vie éprouvante au centre de la discussion. Ainsi, appelé à se prononcer sur les conséquences du trouble somatoforme douloureux sur la capacité de travail de l'intimé, le médecin a répondu: "L'exploré ne se voyait probablement plus capable de travailler [depuis 2001] dans une activité physique exigeante, tenant compte de ses douleurs, subissant ainsi le développement d'un cercle vicieux dans lequel la perte d'espoir aggravait à son tour ses douleurs (rapport d'expertise, p. 38) ". Cet extrait de l'expertise montre que l'appréciation rétrospective du docteur K._ repose uniquement sur des hypothèses qui ne sont étayées par aucun élément objectif extérieur aux impressions subjectives de l'assuré, qui servent de seul fondement aux conclusions de l'expert. Ce faisant, il n'est pas possible de saisir les raisons pour lesquelles le trouble somatoforme douloureux aurait présenté un caractère invalidant avant février 2010. En particulier, pour écarter les constatations de la doctoresse C._, selon lesquelles l'intimé ne présentait aucun trouble psychique limitant sa capacité de travail en 2004 (rapport du 27 décembre 2004, p. 25), le docteur K._ critique les conclusions de son confrère en leur substituant sa propre appréciation onze ans plus tard. Cela ne suffit pas pour mettre en cause l'évaluation de la doctoresse C._ qui, contrairement à ce qu'indique l'expert, a pris en considération les plaintes que lui avait exprimées l'assuré à l'époque de l'examen. Dans ces circonstances, la juridiction cantonale ne pouvait pas ignorer les défauts de l'expertise et retenir le caractère invalidant du trouble somatoforme douloureux, voire des autres atteintes mentionnées dans l'expertise pour la période antérieure à février 2010.
6.3. Finalement, les conclusions du neuropsychologue, telles qu'incluses dans l'expertise du docteur K._ (expertise, p. 15), ne permettent pas non plus de retenir des limitations liées à des troubles cognitifs avant février 2010. L'échelle d'intelligence pour adultes selon Wechsler (WAIS-IV) employée par le neuropsychologue est en particulier un test psychométrique applicable à des personnes scolarisées pendant au moins huit années et appartenant à la population suisse (avis du SMR du 19 août 2015, p. 3). Aussi, en présence d'une personne faiblement scolarisée dans son pays d'origine et illettrée, l'interprétation clinique des résultats a nécessairement prévalu sur leur lecture strictement psychométrique. Il y avait une importante marge d'appréciation pour l'exercice de laquelle les impressions directes quant à la personne soumise à l'examen sont essentielles. Or les observations directes du neuropsychologue se rapportent dans une large mesure à la situation au moment de son examen (du 12 juin 2015). Elles ne mettent par ailleurs pas en évidence d'éléments qui feraient douter, pour la période antérieure à février 2010, de l'appréciation de la doctoresse C._, selon laquelle la capacité d'adaptation de l'intimé n'était pas altérée (rapport du 27 décembre 2004, p. 25).
6.4. Au vu de ce qui précède, la constatation de la juridiction cantonale quant à une incapacité de travail entière pour la période antérieure à février 2010 est insoutenable. Aucune pièce médicale au dossier ne permet de retenir que la situation d'un point de vue psychique se serait modifiée au point d'entraîner, au degré de la vraisemblance prépondérante, une incapacité de travail jusqu'au moment du prononcé administratif.
7.
Bien fondé, le recours doit être admis, le jugement attaqué annulé et la décision du 25 février 2010 confirmée. Cela étant, le présent jugement ne préjuge pas de l'existence d'une aggravation de l'état de santé de l'intimé survenue postérieurement à la décision administrative litigieuse, telle qu'elle a pu notamment être mise en évidence dans le rapport d'expertise de l'Hôpital E._ au regard du diagnostic de trouble somatoforme douloureux. Il convient donc de transmettre le dossier à l'administration et de l'inviter à examiner si les conditions du droit à une éventuelle rente de l'assurance-invalidité sont réalisées pour la période postérieure à février 2010.
8.
Vu l'issue du litige, les frais judiciaires sont mis à la charge de l'intimé (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est admis. La décision de la Cour de justice de la République et canton de Genève, Chambre des assurances sociales, du 10 mars 2016 est annulée et la décision de l'Office de l'assurance-invalidité du canton de Genève du 25 février 2010 confirmée.
2.
Les frais judiciaires, arrêtés à 800 fr., sont mis à la charge de l'intimé.
3.
Le dossier est transmis à l'Office de l'assurance-invalidité du canton de Genève pour qu'il procède conformément aux considérants.
4.
Le présent arrêt est communiqué aux parties, à la Cour de justice de la République et canton de Genève, Chambre des assurances sociales, et à l'Office fédéral des assurances sociales.
Lucerne, le 9 février 2017
Au nom de la IIe Cour de droit social
du Tribunal fédéral suisse
La Présidente : Pfiffner
Le Greffier : Bleicker