We report on a new Early Cretaceous bird from China that sheds significant light on the evolutionary transition between primitive birds with a long bony tail and those with a short tail ending in a pygostyle. A cladistic analysis of basal birds supports the placement of the new fossil as the sister-taxon of all pygostylians. Possessing a unique hand morphology with a phalangeal formula of 2-3-3-x-x and a reduced number of caudal vertebrae lacking a pygostyle, the new specimen reveals anatomical information previously unknown and increases the taxonomic diversity of primitive, non-pygostylian birds. We infer from the specimen that during the evolution of the avian tail, a decrease in relative caudal length and number of vertebrae preceded the distal fusion of caudals into a pygostyle.