The Romualdo Formation (Araripe Basin) is worldwide known for the large number of well-preserved fossils but the dinosaur record is rather scarce. Here we describe a new coelurosaur, which is the first tetrapod recovered from the basal layers of this stratigraphic unit that consist of dark shales. Aratasaurus museunacionali gen. et sp. nov. is known by an incomplete but articulated right hind limb with the distal portion of the femur, proximal half of tibia and incomplete pes. The new species differs from other coelurosaurs by a medial fossa in the tibia and digits II, III and IV being symmetric. The phylogenetic analysis recovered Aratasaurus museunacionali closely related to Zuolong salleei, forming a basal coelurosaur lineage. The paleohistology indicate that the specimen is a juvenile, with an estimated body length around 3.12 m. The new taxon represents the first occurrence of basal coelurosaurians in the Araripe Basin and suggests a widespread distribution of this group during the Lower Cretaceous.