La storia inizia con una bambina, Sheeta, che, per scappare da un gruppo di pirati dell'aria intenzionati a catturarla, scivola dall'aeronave e cade dal cielo su un villaggio. Durante la caduta una misteriosa luce avvolge la piccola, che improvvisamente inizia a galleggiare nell'aria, fino ad atterrare dolcemente nelle braccia di un ragazzo orfano, Pazu, di ritorno alla fine del suo turno in miniera. Dopo averla soccorsa, Pazu la porta nella sua casa.

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. In pochi credono alla sua esistenza, ma Pazu ne è convinto grazie al fatto che suo padre, anni addietro, fotografò parte della imponente struttura.

Pazu racconta che persino nel romanzo I viaggi di Gulliver di Jonathan 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.