Faits: Faits: A. C._, né en 1960, a été victime d'un accident en 1990. Il bénéficie, depuis le 1er avril 1994, d'une rente d'invalidité de 25 % de la Caisse Nationale Suisse d'Assurance en cas d'accidents (CNA). Il a travaillé en dernier lieu en qualité de maçon au service de l'entreprise X._ SA. Le 11 juin 2001, il a déposé une demande de prestations AI en raison de troubles dorsaux. Par décision du 31 octobre 2002, l'Office de l'assurance-invalidité du canton de Neuchâtel (OAI) a rejeté la demande, considérant que le degré d'invalidité qu'il présente (30 %) est insuffisant pour ouvrir droit à la rente. A. C._, né en 1960, a été victime d'un accident en 1990. Il bénéficie, depuis le 1er avril 1994, d'une rente d'invalidité de 25 % de la Caisse Nationale Suisse d'Assurance en cas d'accidents (CNA). Il a travaillé en dernier lieu en qualité de maçon au service de l'entreprise X._ SA. Le 11 juin 2001, il a déposé une demande de prestations AI en raison de troubles dorsaux. Par décision du 31 octobre 2002, l'Office de l'assurance-invalidité du canton de Neuchâtel (OAI) a rejeté la demande, considérant que le degré d'invalidité qu'il présente (30 %) est insuffisant pour ouvrir droit à la rente. B. Par jugement du 13 novembre 2003, le Tribunal administratif du canton de Neuchâtel a rejeté le recours formé par l'assuré contre cette décision. B. Par jugement du 13 novembre 2003, le Tribunal administratif du canton de Neuchâtel a rejeté le recours formé par l'assuré contre cette décision. C. C._ interjette recours de droit administratif contre ce jugement, dont il requiert l'annulation, en concluant, sous suite de frais et dépens, principalement à l'octroi d'une demi-rente d'invalidité dès le 1er janvier 2002, subsidiairement à la mise en oeuvre d'une instruction complémentaire. L'OAI conclut au rejet du recours, tandis que l'Office fédéral des assurances sociales a renoncé à se déterminer.