Egyptens president Abdul Fattah al-Sisi meddelade att Tiran och Sanafir skulle överföras i april, under ett besök av Saudiarabiens kung Salman.
Mer än 150 personer sattes i fängelse i samband med protester om avtalet, även om många senare frikändes eller fick sina domar förkortade efter överklagande.
Den egyptiska regeringen har sagt att den kommer att utmana tisdagens utslag.
Tiran och Sanafir är obebodda och ligger vid mynningen av Akababukten, en strategisk del av Röda havet som gränsar till Israel, Jordanien, Egypten och Saudiarabien.
Egyptiska trupper har varit stationerade där sedan 1950 på Riyadhs begäran.
Sisis beslut i april att överlämna kontrollen över dem till Saudiarabien gav upphov till omfattande kritik.
Presidenten anklagades för att bryta mot konstitutionen och "sälja" öarna i utbyte mot ett biståndspaket på flera miljarder dollar som avtäcktes av kung Salman under hans besök.
Men Sisi insisterade på att Tiran och Sanafir alltid hade tillhört Saudiarabien.
På tisdagen utfärdade Egyptens statsråd, en förvaltningsdomstol, en dom som upphäver Aprils avtal om sjögränser mellan Kairo och Riyadh.
Det sjögränsavtal som undertecknades tidigare i år mellan Egypten och Saudiarabien överraskade många egyptier.
Sedan dess har demonstranter gått ut på gatorna och kallat arrangemanget författningsstridigt och anklagat regeringen för att ge bort egyptiska territorier i utbyte mot biståndspaket och investeringar värda miljarder dollar från Saudiarabien, en stark anhängare av president Sisi.
Några av dessa demonstranter arresterades och anklagades för att störa den allmänna ordningen. Några är fortfarande bakom galler.
Rättegången gjordes av ett antal framstående människorättsadvokater, under ledning av en före detta presidentkandidat, Khaled Ali.
När domen utfärdades, jublade många i rättssalen och sjöng "öarna är egyptiska". Men den rättsliga striden har ännu inte upphört, eftersom beslutet kan överklagas.
Domen förklarade att de två öarna skulle "bli kvar under Egyptens suveränitet".
Om den godkänns av landets högsta förvaltningsdomstol blir den rättsligt bindande.
Statens rättsinstans, som företräder den egyptiska staten i rättegångar, sade emellertid på tisdagskvällen att den skulle ifrågasätta domen, rapporterade den statliga televisionen.
Sisi har knäckt alla meningsskiljaktigheter sedan han ledde militärens störtande av president Mohammed Morsi 2013.
Sedan dess har mer än 1.000 människor dödats och 40.000 tros ha fängslats, de flesta av dem anhängare av Mr Morsi Muslim Brotherhood.
En egyptisk domare har upphävt regeringens beslut att överlämna kontrollen över två Rödahavsöarna till Saudiarabien.