Ulykken skjedde onsdag morgen i distriktet Madiun, øst på øya.
Luftforsvaret opplyser at 15 mennesker overlevde krasjet, og at det fortsatt letes etter savnede.
En lokal tjenestemann forteller at flyet krasjet inn i flere hus før det skled ut i en risåker og begynte å brenne. Minst to av de døde befant seg på bakken da transportflyet styrtet.
LES OGSÅ:
– Flyet er fullstendig ødelagt. Bare halen er igjen, sier tjenestemannen Wardi til fjernsynsstasjonen Metro TV.
Prøver å slukke
Fjernsynsbildene viser folk som desperat prøver å slukke flammene ved å helle bøtter med vann på vraket. Svar røyk stiger opp fra ulykkesstedet, hvor flydeler ligger strødd utover bakken.
Hjelpemannskaper forsøker å evakuere omkomne og skadde, men arbeidet er vanskelig siden flyet ligger i utkanten av en risåker.
Flere titalls personer skal være skadd, og soldater bidrar med å frakte folk bort fra ulykkesstedet på bårer.
Får behandling
Transportflyet av typen C-130 Hercules kom fra hovedstaden Jakarta da det styrtet i landsbyen Geplak, få kilometer fra militærbasen Iswahyudi.
Det var 11 besetningsmedlemmer om bord, i tillegg til 99 passasjerer.
Flere skadde personer får behandling på et sykehus i nærheten av ulykkesstedet.
– Vi behandler fire personer for hjernerystelse og bruddskader, sier legen Restu Kurnia Cahyani.
Det har vært en rekke flyulykker i Indonesia i senere år, både innenfor den sivile og militære luftfarten. Dårlig vedlikehold av fly har vært et problem for flytrafikken i landet.