En un pueblo como todos del planeta Tierra vive Uli, quien, como siempre le dice su padre, Perfecto, cuando le expresa alguna ilusión o deseo, todavía cree en los peces de colores. Es lo que le dice también a su mujer, Laura, que cada día se vuelve más triste, callada e invisible. Una noche, Uli decide marcharse de casa en la bicicleta a la búsqueda de los peces de colores para traérselos a su padre y así demostrarle que existen.
Llega al Val do Eco, en donde un viento rebelde, exiliado del país de Eolo por enfrentarse al huracán Mitch y que también cree en los peces de colores, le da una pequeña caja con un poquito de viento que le ayudará en su aventura. Un unicornio huído del País da Fantasía para conocer mundo, que ya había visto los peces de colores, se ofrece a llevarlo a su espalda.
Arriban a un pueblo abandonado, habitado sólo por Joe Dell, un hombre-sombra que está a punto de dispararle a Uli con su rifle por intruso, pero cuando concoce su viaje le cuenta su historia triste: del indio de una reserva de Nebraska a quien por quemar una bandera en una manifestación le incendiaron su casa con la familia dentro, por lo que se vino a vivir en soledad. Le regala un lápiz de colores para que le dé color a aquello que crea necesario y una goma para que borre lo que no le guste. Uli le borra el rifle y sigue rumbo en el unicornio.
Aterrizan junto al mar: en las rocas de la playa una joven muy hermosa toca al saxo una canción, aunque no puede hablar pues se quedó muda por amor. Encuentra también a un viejo marinero, que le cuenta a Uli que un día ayudó a una sirena a volver del mar, pues había quedado en un charco al bajar la marea; la veía de vez en cando gracias a un pendiente que ella le dejara y se enamoró. Pero un día encontró en el mar el otro pendiente y no volvió a ver a la sirena. Como recuerdo, le da a Uli una caja con los dos pendientes de sirena.
Uli continúa camino entre las nubes. Aparece en un pueblo en guerra en donde se niega a entrar el unicornio. Conoce a un chico de su edad, Marko, cuyo padre está en la guerra; le regala la caja, la goma de borrar y el lápiz de colores. Duerme en lo que fue la escuela y al día siguiente se encuentra con un papel con peces de colores que había pintado Marko, quien, según le explica en una carta, se marchó para un campo de refugiados huyendo del pájaro del mal. En la estación se sube a un tren verde, como le recomendara Marko, que lo llevará "camiño do corazón". Es el único pasajero. Acaba su viaje cuando se mete a toda velocidad por un túnel negro.
Suena entonces el despertador. Uli ya no sabe si tuvo una pesadilla o hizo un largo viaje, aunque encuentra en su mesa de trabajo un dibujo con peces de colores, y en una cajita unos pendientes de coral. Desayuna y marcha contento al colegio, tarareando la canción que un día le oyó tocar a alguien en un saxo.