Zwei junge Menschen begegnen sich und wissen, dass sie füreinander bestimmt sind. Dabei wohnen sie seit Jahren im selben Ostberliner Viertel: Verkäuferin Paula, alleinerziehende Mutter zweier Kinder, und Paul, unglücklich verheiratet, lernen sich in einer Bar kennen. Von nun an treffen sie sich heimlich, verbringen so viele Stunden wie möglich miteinander und erleben eine Liebe, die sie wie ein Strudel mitreißt. Alles um sie herum scheint unwichtig.
Doch Paul, der in den diplomatischen Dienst eingetreten ist, will seine Karriere nicht durch eine Scheidung gefährden, auch wenn seine Frau ihn betrügt. Paula wird ebenfalls von der grausamen Realität eingeholt, als ihr kleiner Sohn bei einem Verkehrsunfall ums Leben kommt. Sie zieht sich von Paul zurück und denkt sogar daran, eine Sicherheitsehe mit einem älteren Verehrer einzugehen.
Als Paul endlich klarwird, dass seine Ehe ihm nichts mehr bedeutet und er ohne Paula nicht mehr leben will, verbringt er Tage und Nächte wartend vor ihrer Wohnungstür, um zu beweisen, wie ernst es ihm ist. Paula gibt schließlich nach, und die Leidenschaft der beiden füreinander blüht erneut auf. Doch Paula stirbt bei der Geburt des gemeinsamen Kindes und lässt Paul allein zurück.

"Die Legende von Paul und Paula" ist einer der erfolgreichsten Spielfilme der DDR. Der Film entwickelte sich in den wenigen Wochen, die sie in der DDR gezeigt wurde, zum Publikumserfolg, nicht nur wegen ihrer zeitnahen Handlung. Die Mischung aus DDR-Wirklichkeit, mit satirischen Spitzen gespickter Flower-Power-Liebe und Deutschrockmusik traf den Nerv des Publikums. Dabei stand der Film zunächst kurz vor einem Aufführungsverbot. Erich Honecker entschied persönlich, dass der Film in die Kinos kommen sollte, da er darin einen Film für die jungen Menschen erkannte.