La storia inizia con una bambina, Sheeta, che per scappare da un gruppo di ceffi intenzionati a catturarla scivola dalla sua aeronave e cade dal cielo su un villaggio. Durante la caduta una misteriosa luce avvolge la piccola e improvvisamente questa inizia a galleggiare nell'aria, fino ad atterrare dolcemente nelle braccia di un ragazzo orfano, Pazu, durante il suo turno in miniera.

Lui la soccorre e la porta a casa sua. La mattina, appena svegli i due fanno subito amicizia, e durante la conversazione Pazu scopre che Sheeta è una discendente del popolo di Laputa, un leggendario castello volante che viaggia nel cielo nascosto dalle nuvole da centinaia di anni. Per questo in pochi credono alla sua esistenza, ma Pazu ne è convinto grazie al fatto che suo padre, anni addietrò fotografò parte della imponente struttura. Pazu racconta che persino nel romanzo I viaggi di Gulliver di J. Swift vi è una descrizione del castello. Il ragazzo decide quindi di aiutarla a ritornare nella sua città e insieme intraprendono una lunga avventura, costantemente inseguiti dai pirati e dall'esercito.

Al contrario della maggior parte degli altri lavori di Hayao Miyazaki, in Laputa la classica componente "Uomo vs. Natura" è meno marcata. Seppure Sheeta si preoccupi particolarmente della morte e la distruzione durante le battaglie, non si presentano mai spunti naturalistici come nei lavori quali Nausicaä (in cui la protagonista arriva a rischiare la propria vita per salvare la vita ad un cucciolo di mostrotarlo) o Principessa Mononoke.

Va ricordato però che la natura svolge comunque un ruolo importante anche in questo lavoro. Indicativa la scena finale in cui Laputa si spoglia della tecnologia, aggiunta evidentemente dall'uomo, per tornare alla forma originale, ovvero un enorme albero.