A new tracksite with bird footprints, found in the Bardenas Reales de Navarra Natural Park (Navarre, Spain), is presented in this study. The footprints are preserved in four sandstone blocks of the Lerín Formation from the northwest sector of the Ebro Basin. According to the magnetostratigraphic data, the age of these blocks is 20.4 Ma (Agenian, lower Miocene). The footprints are more than 100 mm in length, mesaxonic, and tridactyl, and have a prominent central pad impression with the digit impressions not jointed proximally. These features allow classifying them as Uvaichnites riojana. Some of the studied footprints are better preserved than the type series of Uvaichnites, which were found also in the northwest sector of the Ebro Basin. Therefore, the original diagnosis has been emended. Available chronostratigraphic data for these localities as well as for other footprints from China indicate a latest Oligocene-earliest Miocene age (from about 23 to 20 Ma) for Uvaichnites-like footprints. Sedimentological data also indicate similar continental environments, namely perilacustrine deltaic systems and distal alluvial systems. The information about early Miocene avian remains (bones, eggs and footprints) in the Iberian Peninsula is scarce. The skeletal and oological record of this age has been included within the families Phoenicopteridae, Phaisanidae and Cathartidae (or incertae sedis), while the ichnological record was related with trackmakers belonging to Charadriiformes, Ardeidae and Gruidae taxa. For this scenario, in which there are few avian remains, the ichnological diversity shown in this paper complements and improves the knowledge about the Iberian avian diversity in the early Miocene.