Kyrkan i Tabgha är byggd där de kristna tror att Jesus utförde underverket av bröd och fiskar, även känd som utfodring av de 5.000.
Hebreisk graffiti på en vägg tros tyda på att attacken kan ha varit ett verk av judiska extremister.
Polisen häktade 16 tonåringar för förhör, men släppte dem senare.
Spokeswoman Luba Samri berättade för AFP nyhetsbyrån att de frigavs "utan villkor, efter att ha blivit intervjuade och ge uttalanden".
BBC:s Kevin Connolly i Jerusalem säger att Tabgha är en helig plats för de tusentals kristna pilgrimer som besöker det heliga landet varje år.
Mordbrandsattacken på kyrkan av multiplikationen av Loaves och Fiskar orsakade omfattande skador på en bokhandel och andra byggnader vid komplexet men förstörde inte 5th Century mosaik golv som är dess viktigaste arkeologiska särdrag.
Två personer som hade bott på anläggningen fördes också till sjukhus som led av rökinandning.
En vers från en hebreisk bön som fördömde dyrkan av "idoler" hittades sprejmålad i rött på en vägg i kyrkan.
Våra korrespondenter säger att graffiti kommer att antyda för många att attacken är en del av en sporadisk kampanj av en liten grupp judiska högerextremister mot icke-judiska mål i Israel, men polisen sade att det var för tidigt att berätta.
"Att bränna kyrkan är en feg och föraktlig handling som strider mot Israels grundläggande värderingar", sade inrikessäkerhetsminister Gilad Erdan i ett uttalande.
Den israeliska påtryckningsgruppen, Rabbis for Human Rights, säger att det har förekommit 43 hatbrottsattacker mot kyrkor, moskéer och kloster i Israel och den ockuperade Västbanken sedan 2009, Reuters nyhetsbyrå rapporterar.
Arsonister tros ha startat en brand som har skadat en romersk - katolsk kyrka vid Galileiska sjön i norra Israel, säger polisen.