Marlin è un pesce pagliaccio che sta per diventare papà: la sua moglie Coral ha deposto migliaia di uova, e i due stanno aspettando che si schiudano. Ma all'improvviso un barracuda li attacca e divora Coral e le uova. Marlin, vedovo e disperato, scopre però che un uovo (uno solo) si è salvato, e decide di chiamare quell'unico figlio rimastogli Nemo, come era desiderio di sua moglie, e si promette di non fargli succedere mai assolutamente nulla.

Nemo nasce e poi cresce, e Marlin riversa su di lui tutte le premure possibili, terrorizzato che si possa far male e che gli possa capitare qualunque cosa anche di poco conto.
Tra l'altro Nemo è nato con una pinna atrofica (più piccola delle altre), e questo rende ancora più ansioso il padre. Il primo giorno di scuola di Nemo riempie il padre di grandi preoccupazioni poiché il maestro Ray, una enorme razza-manta "aquila di mare", ha intenzione di portare Nemo i suoi compagni di classe a fare un salto nel blu ed esplorare l'oceano aperto. Imbarazzato dalla sfuriata del troppo premuroso padre, Nemo, come gesto di ribellione, entra in mare aperto per toccare un motoscafo con la pinna, ma mentre sta tornando indietro viene catturato con un retino da un subacqueo, che poi sale sul motoscafo insieme ad un altro subacqueo e si allontana. Marlin, disperato come non mai, tenta l'inseguimento, ma il motoscafo è troppo veloce e le eliche creano un vortice di bolle che impedisce al pesce di avvicinarsi, e per di più il sub aveva stordito Marlin con il flash della fotocamera. Dal motoscafo però cade una maschera, con scritto sulla fascia un indirizzo: "P. Sherman, 42 Wallaby Way, Sydney, Australia".

Marlin non sa leggere, ma mentre vaga alla ricerca del motoscafo che ha rapito suo figlio incontra per caso Dory, una pesciolina chirurgo che soffre di gravi perdite di memoria a breve termine, e quindi non ricorda mai assolutamente nulla di ciò che è successo poco prima. Lei dice di aver visto la barca e di seguirla per trovarla, ma dopo poco, non ricordandosi, gli urla di smetterla di seguirla. Mentre i due stanno quindi per separarsi, vengono avvicinati da un enorme squalo bianco di nome Bruto: Marlin è quasi paralizzato dal terrore, mentre Dory è completamente ignara del pericolo ed acconsente a seguire Bruto alla riunione di un gruppo di autoaiuto di squali "buoni" che vogliono smettere di mangiare pesci. Il gruppo, composto da Bruto, da Randa (uno squalo martello) e da Fiocco (una verdesca con un amo piantato nel naso) ha la sua sede di riunione nel relitto di un sottomarino circondato da centinaia di mine attive (che Dory scambia per palloncini). Mentre Marlin cerca, con poco successo, di raccontare una barzelletta per alleviare la situazione, vede la maschera appesa ad un siluro e commuove gli squali raccontando la tragica scomparsa di suo figlio Nemo. Dory, che conosceva già la storia ma se n'era ovviamente dimenticata, cerca di aiutare Marlin a recuperare la maschera, ma si ferisce al naso con l'elastico: l'odore di sangue scatena Bruto, che dimentica la promessa e insegue Dory e Marlin per divorarli. I due si nascondono in un tubo di lancio, ma i violenti colpi di Bruto, che cerca di raggiungerli, fanno uscire il siluro, che va a finire su una mina e provoca quindi una grossa esplosione.

Intanto, Nemo si ritrova in uno strano ambiente che scopre essere un acquario (dopo aver visto le decorazioni e sbattuto contro il vetro), dove fa amicizia con gli altri pesci abitanti, che gli rivelano quale sarà il suo destino: essere regalato a Darla, l'orrida nipotina del dentista, proprietario dell'acquario e suo rapitore, nota per riuscire ad annientare in breve tempo qualsiasi pesce che le capiti in mano. Il capo dei pesci dell'acquario è Branchia, un idolo moresco piuttosto anziano. Branchia è l'unico altro pesce assieme a Nemo a provenire dall'oceano invece che da un negozio, e da anni sogna la fuga (al punto da aver tentato di saltare nel gabinetto, finendo invece sugli strumenti metallici del dentista ferendosi una pinna). Vedendo il piccolo Nemo, Branchia organizza un piano: Nemo dovrà provare ad entrare nella pompa del filtro dell'acqua (è l'unico abbastanza piccolo per passarci) e bloccare la valvola del flusso incastrando nelle pale un sassolino, in modo che l'acquario si sporchi e si riempia di alghe in pochi giorni. In questo modo i pesci sperano di costringere il dentista a tirarli fuori dalla vasca per pulire l'acquario ed a metterli in sacchetti di plastica, con i quali avrebbero potuto rotolare giù dal davanzale fino in strada e tuffarsi in oceano.

Intanto nell'oceano Marlin e Dory si risvegliano sul relitto del sottomarino, finito in bilico sopra un'enorme fossa oceanica. Mentre cerca di recuperare la maschera, ma questa cade nell'abisso e i due pesci la inseguono. Nel buio più profondo, i due vengono attratti da una bella luce, che però si muove: in realtà essa non è altro che l'esca di un mostruoso e famelico Pesce Lanterna degli abissi. In preda al panico, Marlin cerca di tenere a bada il pesce mentre Dory, grazie alla luce, riesce a leggere la scritta sulla maschera. Usciti dall'abisso, Marlin chiede a Dory se ricorda la scritta, e lei la recita tutta d'un fiato: è la prima cosa da anni che riesce a non dimenticare.

Dopo un diverbio, e dopo aver chiesto indicazioni ad un branco di pesci argentati, i due pesci scoprono che per arrivare a Sydney bisogna imboccare la C.O.A., una corrente acquatica australiana. Marlin si allontana subito entusiasta, ma i pesci trattengono Dory e l'avvertono che prima della corrente c'è un pericoloso crepaccio, e sottolineano che bisogna attraversarlo sul fondo e non in superficie. Marlin, ignaro del consiglio perché Dory non gliel'ha detto chiaramente, si impunta a voler passare in superficie; i due avvistano immediatamente la corrente, ma poi si ritrovano in mezzo a un gigantesco banco di meduse rosa del tipo Chrysaora fuscescens. Marlin è in parte immune al veleno, perché vive dentro un anemone ed è abituato alle punture, ma Dory no, e rimane intrappolata nel banco: Marlin riesce a tirarla fuori, ma le punture avute sono troppe, e i due pesci perdono conoscenza e svengono.

Si risvegliano poi sul dorso di un branco di tartarughe carette, che sta viaggiando lungo la C.O.A.. Qui Marlin ha un esempio di padre completamente diverso da lui, poiché Scorza, la tartaruga con cui ha fatto amicizia, ha un figlio molto spericolato (di nome Guizzo) su cui però non interviene, affermando che deve fare le sue esperienze e cavarsela in solitaria. Usciti dalla corrente, i due si ritrovano in una zona di mare desolata, dove cercano indicazioni e vedono quella che si rivela essere una balenottera azzurra: Dory afferma di saper parlare il "balenese", ma i versi che emette non sembrano avere un effetto positivo, perché la balena si avvicina e li aspira nella sua enorme bocca insieme a un banco di krill. Anziché inghiottirli, però, la balena li trasporta al porto di Sidney, dimostrando di aver capito le strampalate indicazioni di Dory.

Qui Marlin incontra il pellicano Amilcare, amico dei pesci dell'acquario, che porta i due fino allo studio del dentista mettendoli nel suo grande becco riempito d'acqua. Il piano dei pesci è stato messo in atto con successo, ma alla fine non ha funzionato, perché il dentista non ha pulito personalmente la vasca ma ha installato un filtro elettronico a raggi ottici che analizza continuamente l'acqua per tenere costantemente pulito l'acquario; quando Dory e Marlin arrivano, il dentista sta regalando Nemo alla nipotina, che come ultima speranza si finge morto nella speranza di essere buttato nel water e di poter così raggiungere il mare. Marlin, però, crede che il figlio sia veramente morto, e dopo essersi fatto ritrasportare al porto, in preda alla disperazione, abbandona Dory nonostante le sue suppliche.

Intanto, grazie a un intervento dei pesci nell'acquario (Branchia che si fa letteralmente sparare fuori con un getto di bolle) Nemo finisce catapultato nel piccolo lavandino del dentista e attraverso le fogne raggiunge il mare: qui incontra Dory che sta vagando senza meta, completamente disorientata e smemorata, e si offre di aiutarla. Dory sulle prime non lo riconosce, ma improvvisamente tutto le torna alla memoria sentendo il nome del pesciolino e conduce Nemo da suo padre, che subito lo abbraccia: i tre tornano a casa insieme, profondamente cambiati dall'avventura che hanno vissuto. Marlin non è più un padre così apprensivo, e Nemo ha imparato ad avere fiducia in sé stesso, mentre Dory ha ritrovato i suoi amici squali e fa progressi contro i suoi buchi di memoria.

Subito dopo la fine del film viene fatto vedere cosa succede ai pesci dell'acquario in cui era stato imprigionato Nemo: il nuovo filtro acquistato dal dentista si rompe, e stavolta egli è costretto a pulire personalmente l'acquario, tirando fuori i pesci e mettendoli in dei sacchetti di plastica. Allora essi ne approfittano e mettono in atto il piano ideato da Branchia che era fallito la prima volta, e rotolano fino al mare. Ma una volta tuffatisi, si rendono conto che non potranno più uscire dai sacchetti di plastica, e si capisce quanto il piano di Branchia non fosse così perfetto come lui l'aveva definito.