Paul Heyse was born on 15 March 1830 in Heiliggeist Strasse, Berlin. His father, Karl Wilhelm Ludwig Heyse, was a professor of classical philology who had been the tutor of both Wilhelm von Humboldt's youngest son (1815 – 17) and Felix Mendelssohn (1819 – 27). The mother, Julie Heyse, came from the wealthy and art loving family of the Prussian court jeweller Jakob Salomon (who took the surname Saaling after his conversion to Christianity) and was a cousin of Lea Mendelssohn, the composer's mother. Heyse attended the renamed Friedrich-Wilhelms-Gymnasium until 1847. He was later remembered as a model student. His family connections gained him early entry to the artistic circles of Berlin, where he made the acquaintance of Emanuel Geibel, a man fifteen years his elder who was to become his literary mentor and lifelong friend, and who introduced him to his future father-in-law, the art historian and writer Franz Kugler.

After leaving school Heyse began studying classical philology. He met Jacob Burckhardt, Adolph Menzel, Theodor Fontane and Theodor Storm, and in 1849 joined the Tunnel über der Spree literary group. Frühlingsanfang 1848, the first of Heyse's poems to see print, expressed his enthusiasm for the recent Revolution. After a brief excursion to see the student militias he returned home without joining them, apparently out of consideration for the concerns of his parents and friends.

Having studied for two years at the University of Berlin he left for Bonn in April 1849 in order to study art history and Romance languages. In 1850 he finally resolved on a career as a writer and began a dissertation under the supervision of Friedrich Diez, a pioneer of Romance philology in Germany; but when it was discovered he was conducting an affair with the wife of one of his professors he was sent back to Berlin. Heyse's first book, Der Jungbrunnen (a collection of tales and poetry) was published anonymously by his father that same year. About the same time, Heyse received from the publisher Alexander Duncker a manuscript by the then unknown Theodor Storm. Heyse's enthusiastic critique of Sommergeschichten und Lieder laid the foundations of their future friendship.

In 1851, Heyse won a contest held by the members of the "Tunnel" for the ballad Das Tal von Espigno. His first short story, "Marion" (1852), was similarly honoured, and it was followed by the Spanische Liederbuch, translations by Geibel and Heyse, a book of songs which was to be a favourite with composers. Throughout his career Heyse worked as a translator, above all of Italian literature (Leopardi, Giusti).

Several members of the "Tunnel" began to find its formalities and public nature distasteful, and a smaller circle, the Rütli, was formed in December 1852: it included Kugler, Lepel, Fontane, Storm, and Heyse.

In May 1852 Heyse was awarded a doctorate for his work on the troubadours, and a Prussian scholarship allowed him to depart for Italy to look for old Provençal manuscripts. He made friends with Arnold Böcklin and Joseph Victor von Scheffel but was banned from the Vatican library after being discovered copying passages from unpublished manuscripts. He returned to Germany in 1853, where, with the Italian landscape still fresh in his mind, he wrote the works which first made him famous: the tragedy Francesca von Rimini; his most famous short story, "L'Arrabbiata" ("The Fury", 1853, published in 1855); and the Lieder aus Sorrent ("Songs of Sorrento", 1852/53). Much of his new writing appeared in the Argo, the yearbook of the Rütli writers.

Emanuel Geibel persuaded the King of Bavaria, Maximilian II, to grant Heyse a titular professorship in Munich. Heyse was thus appointed professor of Romance philology, although he never taught at that city's university. After his marriage on 15 May to Margarete Kugler he arrived in Munich on 25 May 1854. At his first audience with the King, Heyse presented his verse tales, Hermen, and began a productive life as one of the Nordlichtern ("northern lights": Geibel, Heyse and Riehl) and establishing another literary society, Die Krokodile, which included Felix Dahn, Wilhelm Hertz, Hermann Lingg, Franz von Kobell, the cultural historian Wilhelm Heinrich Riehl, Friedrich Bodenstedt, and the travel writer and art patron Adolf Friedrich von Schack. In December Heyse began a long correspondence with Eduard Mörike.

On 22 August 1855 Heyse's first son, Franz, was born. Heyse would have four children by his first marriage: Franz (1855 - 1919), Julie or Lulu (Frau Baumgarten, 1857 - 1928), Ernst (1859 - 1871) and Clara (Frau Layriz, 1861 - 1931). In 1859, obligations to the Kugler family led Heyse to take up a position as editor of the Literaturblatt zum deutschen Kunstblatt, and he declined a tempting offer from the Grand Duke Carl Alexander von Weimar which would have involved moving to Thuringia.

On 30 September 1862, his wife Margarete died in Meran of a lung illness. He completed the historical drama, Ludwig der Bayer — a Bavarian period piece which Maximilian II had long been eager to see — but its theatrical production was a failure. Nevertheless Heyse worked throughout the 1860s on new plays, eventually achieving his greatest success with Kolberg (1865).

He married Anna Schubart in 1867. Over the next three decades, Heyse continued to write prolifically. Despite a number of bereavements his life was uneventful, and his fame grew steadily until he was a world famous figure. He was a very early opponent of naturalism, making critical references to it in print long before its influence could be felt in Germany. Younger critics who favoured naturalism made attacks on his writings, to which he replied in Merlin (1892): but their influence on the public was negligible. He was dubbed Dichterfürst, prince of poetry, and he worked tirelessly to promote international understanding within Europe. In 1900, he was named an honorary citizen of Munich, and several special publications honoured his 70th birthday; and in 1910, he was made a member of the nobility, before being awarded the Nobel Prize for Literature on 10 December. He could not attend the ceremony, and was represented in Sweden by Count von Pückler.

His last published works were Letzten Novellen and Italienischen Volksmärchen (1914). He died on 2 April 1914, several months before the outbreak of World War I, and was buried in the old section of the Waldfriedhof (Nr. 43-W-27).