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.