Faits: A. A._, ressortissant somalien né en 1970, a travaillé en qualité d'employé d'exploitation. Le 13 octobre 2009, il a déposé une demande de prestations auprès de l'Office de l'assurance-invalidité pour le canton de Vaud (l'office AI), invoquant une atteinte dégénérative de la colonne lombaire. Dans le cadre de l'instruction de la demande, l'office AI a recueilli des renseignements auprès du docteur H._, spécialiste FMH en médecine interne générale, médecin traitant, qui a transmis un rapport de la doctoresse B._, spécialiste FMH en médecine physique et réadaptation, médecin traitant, du 19 janvier 2009. L'administration a alors interpellé celle-ci (rapport du 26 octobre 2009), les docteurs L._, spécialiste FMH en médecine du travail, et C._, spécialiste FMH en médecine interne, médecins auprès de l'unité de médecine du personnel de l'Hôpital X._ (rapport du 5 novembre 2009), et le professeur K._, chef de service auprès de la Division de l'Hôpital X._. Ce médecin a mis en évidence un ralentissement, des difficultés attentionnelles ainsi que des troubles mnésiques antérogrades modérés (rapport non daté faisant suite à un examen neuropsychologique réalisé le 10 novembre 2009). Pour compléter ces données, l'administration a chargé le Centre Z._ de la réalisation d'une expertise. Les docteurs J._, spécialiste FMH en rhumatologie, et S._, spécialiste FMH en psychiatrie et psychothérapie, ont retenu les diagnostics sans répercussion sur la capacité de travail de pied bot congénital droit opéré à l'âge de 3 ans, de rachialgies communes sans lésion anatomique susceptible de les expliquer, de syndrome douloureux somatoforme persistant ainsi que de troubles anxieux et dépressifs mixtes. L'assuré disposait selon eux d'une capacité de travail entière dans toute activité (rapport du 12 octobre 2010). Sur la base de ces éléments, l'office AI a envisagé de refuser à A._ l'octroi de toute prestation au motif qu'il ne présentait pas d'atteinte invalidante à la santé (projet de décision du 16 mars 2011). Faisant part à l'administration de ses objections, l'assuré lui a transmis des rapports médicaux émanant des doctoresses M._, spécialiste FMH en psychiatrie et psychothérapie (rapport du 30 juin 2011) et B._ (rapport du 22 juillet 2011). La première a retenu un trouble anxieux dépressif mixte ainsi qu'un état de stress post-traumatique et la seconde des rachialgies chroniques dans un contexte de discopathies sévères L3-L4, discopathies modérées L4-L5 et L5-S1 et protrusion discale L5-S1 médiane et médio-bilatérale sans conflit radiculaire, des douleurs sacro-coccygiennes sur probable ancienne subluxation des dernières pièces coccygiennes, des arthralgies multiples d'origine indéterminée, des séquelles de pied bot à droite avec amyotrophie du membre inférieur droit, status après intervention chirurgicale dans l'enfance au niveau de l'arrière pied et du tendon d'Achille, une carence en vitamine D corrigée, un état de stress post-traumatique et des troubles neuropsychologiques d'origine indéterminée. L'office AI a maintenu sa position (décision du 10 octobre 2011). B. L'assuré a déféré cette décision au Tribunal cantonal du canton de Vaud, Cour des assurances sociales. Il a produit un rapport de la doctoresse P._, médecin auprès de la clinique Y._ (rapport du 4 octobre 2011). Le tribunal cantonal l'a débouté, considérant qu'il présentait une capacité de travail entière dans toute activité (jugement du 25 février 2013). C. A._ interjette un recours en matière de droit public contre ce jugement dont il demande l'annulation. Il conclut au renvoi de la cause au tribunal cantonal, subsidiairement à l'office AI, pour instruction complémentaire et nouvelle décision. 