Los datos más fidedignos establecen que la historia de Aldeanueva de Ebro comienza en la Reconquista. En 1045 García Sánchez III de Navarra conquista Calahorra y, tras la línea fronteriza, quedan extensas superficies aptas para pastizales. Gestes de Calahorra y Cameros se establecen en esta zona y forman un enclave que al ir creciendo se conoce por "el lugar de Aldeanueva", que es la terminología que se utiliza para designar al pueblo antes de pasar a la categoría de villa.

El paso de aldea a villa se hace el 25 de marzo de 1664, pero este paso fue dificultuso y estuvo acompañado de motines populares, algaradas, insultos y destierros.

Felipe IV, que necesitaba dinero para las arcas reales, decide vender parte de los terrenos propiedad de la corona. Por Arnedo de Ebro, que es el apelativo con el que se conocía entonces a Aldeanueva, establece un precio de 4.125.000 maravedíes de plata, que aparece dispuesto a pagar Juan Manuel Iñiguez de Arnedo, pero los aldeanos tenían derecho de retracto, es decir, podían comprar su propia jurisdicción y, de esa forma, librarse de toda dependencia ajena. Deciden ejercer este derecho y, tras numerosos problemas, acaban de amortizar pagos y rentas en 1924.