... Nelson strandet nach einem missglückten Raketenstart auf einer einsamen Insel im Pazifik. Dort findet er eine Flasche, die einen weiblichen Flaschengeist beherbergt. Als er die 2000 Jahre gefangene „Jeannie“ befreit und sie ihn rettet, schenkt er ihr die Freiheit.
Falsch gedacht, Jeannie hat sich in ihren neuen Meister verliebt und folgt ihm nach Cocoa Beach in Florida. In ihrer Naivität versucht sie Tony durch ihre Zauberei zu helfen, zu schützen und zu erfreuen. Doch jedes Mal geht etwas schief und dank ihrer chronischen Eifersucht sogar noch mehr.
Schon bald zieht er die Aufmerksamkeit seines unmittelbaren Vorgesetzten, den NASA-Psychiater Dr. Col. Alfred Bellows, auf sich. Einziger Rückhalt für Tony ist sein bester Freund und Arbeitskollege Roger Healey. Einige Zeit nach Tonys Rettung von der Insel „findet“ er Jeannie zufällig.
Seitdem haben sowohl Roger als auch Tony alle Hände voll zu tun, um in ihren verrückten Abenteuern weder getötet noch entlassen zu werden.