Faits: A. A._ a été engagé dès le 13 septembre 1999 en qualité de maçon par l'entreprise X._ SA. Le 2 avril 2009, il a glissé et chuté sur son côté gauche en enjambant un muret sur un chantier alors qu'il portait de lourds outils. Bien qu'il ait ressenti des douleurs dans la région axillaire, l'épaule et le bras gauches et rencontré des difficultés à effectuer certains mouvements, il a continué à travailler jusqu'au 30 avril 2009 avant de consulter un médecin. Dès cette date, il a cessé d'exercer toute activité lucrative. La Caisse nationale suisse d'assurance en cas d'accidents (CNA) a pris en charge le cas. Se fondant notamment sur le résultat d'une arthro-IRM de l'épaule gauche effectuée le 18 juin 2009, le docteur C._, spécialiste FMH en médecine interne, a posé le diagnostic de rupture du tendon du sus-épineux, d'atteinte partielle du sous-scapulaire et dans une moindre mesure du sous-épineux (rapport du 3 juillet 2009). Le 15 décembre 2009, A._ a déposé une demande de prestations auprès de l'Office de l'assurance-invalidité du canton de Neuchâtel (ci-près: l'OAI). Dans le cadre de l'instruction de la demande, l'OAI a confié la réalisation d'une expertise au docteur U._, spécialiste FMH en rhumatologie et en médecine interne. Ce praticien a retenu comme diagnostics avec répercussion sur la capacité de travail, des omalgies bilatérales chroniques, un syndrome lombo-vertébral récurrent sans signe radiculaire irritatif ou déficitaire (discopathie L4-L5 sans conflit radiculaire), un syndrome cervico-brachial récurrent sans signe radiculaire irritatif ou déficitaire (discopathie multi-étagée modérée) et un syndrome polyinsertionnel douloureux récurrent (diminution du seuil de tolérance à la douleur). Il a conclu à une capacité de travail de 80 % dans une activité adaptée, c'est-à-dire respectant les limitations fonctionnelles suivantes: les mouvements en porte-à-faux répétitifs de manière prolongée, le port de charges de plus de 10 kilos ainsi que les mouvements des membres supérieurs au-dessus de l'horizontale (cf. rapport d'expertise du 18 octobre 2010 et correctifs et complément des 10 mars et 5 juillet 2011). Par décision du 15 février 2011, confirmée sur opposition le 26 août 2011, la CNA a alloué à A._, dès le 1 er novembre 2010, une rente d'invalidité de 25 %, ainsi qu'une indemnité pour atteinte à l'intégrité fondée sur un taux de 19 %. Se fondant sur les conclusions de l'expert U._, l'OAI a octroyé à l'assuré une demi-rente d'invalidité dès le 1 er juin 2010 (cf. décision du 13 octobre 2011). B. Saisie d'un recours contre la décision de l'OAI, la Cour de droit public du Tribunal cantonal neuchâtelois l'a rejeté par jugement du 17 janvier 2013. Par jugement du même jour, cette même Cour a partiellement admis le recours contre la décision sur opposition de la CNA du 26 août 2011. Elle l'a annulée en tant qu'elle constatait que l'indemnité pour atteinte à l'intégrité n'était pas contestée et renvoyé la cause à la CNA pour instruction complémentaire et nouvelle décision sur ce point. Elle a rejeté le recours pour le surplus. C. A._ interjette un recours en matière de droit public contre le jugement du 17 janvier 2013 en matière d'assurance-invalidité, en concluant à l'octroi d'une rente entière d'invalidité dès le 1 er juin 2010. Tant l'OAI que l'Office fédéral des assurances sociales ont renoncé à se déterminer. D. Par arrêt de ce jour, le Tribunal fédéral a rejeté le recours de l'assuré contre le jugement cantonal du 17 janvier 2013 en matière d'assurance-accidents (8C_149/2013).