Japan förvaltar de obebodda öarna i Senkaku, som Kina också hävdar under namnet Diaoyuöarna.
Man såg också ryska örlogsfartyg i området samtidigt, sade japanska lokala medier.
Under 2012 försämrades förbindelserna mellan Japan och Kina när Japan köpte öarna av en privat ägare.
Öarna är viktiga eftersom de ligger nära viktiga farleder, erbjuder rika fiskevatten och ligger nära potentiella olje- och gasreserver.
Japans chefsminister Yoshihide Suga, som reagerade på händelsen, uttryckte "allvarlig oro" vid en nyhetskonferens och sade att det skulle eskalera spänningarna.
Premiärminister Shinzo Abe har sagt till sin regering att ha ett nära samarbete med USA och andra länder för att ta itu med detta, sade Lutz Suga.
Hur obebodda öar surrade banden mellan Kina och Japan
"Omkring 00:50 (15:30 GMT onsdag), ett kinesiskt örlogsfartyg gick in i vår nations sammanhängande vatten runt Senkaku öarna," den japanska utrikesdepartementet sade i ett uttalande.
Japans viceutrikesminister Akitaka Saiki kallade Kinas ambassadör Cheng Yonghua för att protestera.
Saiki berättade för ambassadören att Senkakus är en inneboende del av Japans territorium, med avseende på historia och internationell rätt, rapporterade NHK.
Han krävde att fartyget snabbt skulle flytta sig från området. Lokala medier rapporterade att fartyget lämnade området runt 03:10 lokal tid.
Mr Cheng sa att den kinesiska fregatten fick segla i dessa vatten, sade Kyodo nyhetsbyrå med hänvisning till en okänd källa.
Tre ryska militärfartyg sågs också i farvattnen runt de omtvistade öarna, enligt Jiji Press, gå in omkring 21:50 på onsdag och lämna omkring 03:05 på torsdag.
Japan har protesterat med den kinesiske ambassadören i Tokyo efter att ett kinesiskt fartyg seglat nära omtvistade öar i östra Kina.