Baserat på de omgivande klippornas ålder är detta den tidigaste kända medlemmen av kladden som producerade dagens fåglar: Ornituromorpha.
Den skjuter tillbaka förgreningen av denna evolutionära grupp med minst fem miljoner år.
Den lilla fågeln verkar ha varit en vadare som kunde flyga vilt.
Upptäckten redovisas i tidskriften Nature Communications.
Fåglarna började utvecklas från dinosaurierna för omkring 150 miljoner år sedan i slutet av den jurassiska perioden. Detta är åldern för den berömda men varmt ifrågasatta "första fågel" Archaeopteryx - nu anses av många vara en befjädrad dinosaurie.
Omkring 20 miljoner år senare, när den nyfunna arten vadade och fladdrade genom vad som skulle bli nordöstra Kina, tror paleontologerna att det fanns en hel del olika fågelliv.
Ungefär hälften av dessa arter var Enantiornithes, en grupp tidiga fåglar med tänder och klor vingar som så småningom alla dog ut.
Den andra halvan, inklusive det nya fyndet, var Ornithuromorpha - en grupp som så småningom gav upphov till moderna fåglar och såg mycket mer ut som dem.
Den grenning som ligger bakom denna kluvna mångfald är vad den nya upptäckten skjuter tillbaka i tiden; tidigare var den tidigaste kända Ornithuromorph 125 miljoner år gammal.
De skelettpar som definierar den nya arten, döpte Archaeornitura meemannae, grävdes upp från Sichakoubäckenet i Hebeiprovinsen.
"Den nya fossilet representerar den äldsta rekordet av Ornithuropmorpha", sade den första författaren Wang Min, från den kinesiska vetenskapsakademin i Peking. "Den skjuter tillbaka ursprungsdatumet med minst fem miljoner år."
Exemplen var väl bevarade och avslöjade ett antal detaljer om A. meemannae. Fågeln stod omkring 15 cm lång och dess ben, även på de övre delarna, hade inga fjädrar, vilket tyder på en vadande livsstil.
Benens storlek och form tyder också på god manövrerbarhet i luften.
Forskare i Kina har beskrivit en ny art av tidig fågel, från två fossil med intakt fjäderdräkt som daterar sig till 130 miljoner år sedan.