The theme of romantic love is nearly as old as literature itself, but romance in the original definition meant a novel or work in the vernacular (as in, "Romance languages"), and from there came to be associated with work dealing with chivalry (e.g. Arthurian romance), which often emphasized courtly love; and more broadly still with works that featured mystery, excitement, adventure, and unusual incidents - which brings us roughly to the 17th century with subgenres like the picaresque novel; this definition was still prominent in discussing literature and film into the mid-20th century.
Before the romance novel proper came out, you had individual novels with heavy romantic plots - such as Pamela, or Virtue Rewarded (1740), which in turn inspired their more erotic counterparts, such as Justine, or the Misfortunes of Virtue (1791). These kind of plots were perennial, but didn't gel into what we'd consider contemporary genres; they were almost always a combination of romantic love-interest, unusual incidents, mystery, action, etc. 19th century novels like Pride and Prejudice (1813) and Jane Eyre (1847) were literary novels that served as precursors to what would become the fiction genre of romance, in that they focused primarily on the romantic relationship, and especially female protagonists and their internal life and emotions, as the driving force of the novel.
During the late 19th and early 20th century period of nickel weeklies, dime novels, and then pulp magazines, romance began to emerge as distinct genres - early science fiction, for example, was labeled as "scientific romance" or in the case of Edgar Rice Burrough's Mars novels, "planetary romance"; historical fiction was often marketed as "historical romance," etc. Many of these, in addition to whatever exotic setting or elements, often had some genuine romantic element as far as boy-meets-girl (or hero-meets-underclad-alien-princess), but were usually not focused solely or even primarily on the relationship, and rarely featured female protagonists...but there were pulps and novels that did.
Romance pulps like Love Story, Love Book, Gay Love, Cupid's Diary, and Rangeland Romances and the closely-allied field of "confessionals" such as True Confessions, I Confess, Real Love, etc. were aimed primarily at a female audience (and, unusually for pulps at the time, had a larger number of female writers and editors), and were the real basis of mass-market romance fiction of today: they were focused almost exclusively on women and their romantic relationships. Their more upstanding counterparts in the more upscale or "slick" magazines included Red Book and hardback romantic fiction novels, which were often sold as general fiction.
In the 1930s and 40s, as the pulps peaked and waned, romance writing shifted - both to comic books Young Romance, Young Love, Negro Romance, Sweethearts, etc. - and to the emerging pulp paperback novel, which included the daring gay and lesbian pulp novels, but also much more mainstream mass market affairs aimed at a growing audience of literate women.
A major force in this vein was Harlequin Enterprises, which was founded in Canada in 1949 and began pushing romance novels in the United States in 1957. Harlequin, and its various competitors and imitators, found a market with tastes for the pulp-style romantic story (although often more explicit than the pulps or comics allowed) for the contemporary romance novel and started the trend which is still going strong today.
Because this new brand of romantic fiction contained more explicit sexuality, it more often came under fire for crossing or almost crossing the line into actual pornographic territory, which was the subject of obscenity laws. In 1960, for example, Penguin was sued in the UK for publishing the unexpurgated text of Lady Chatterley's Lover (1928); in 1961 the publication of Tropic of Cancer (1934) brought a wave of obscenity lawsuits in the United States. The success of the defendants in those cases opened things up a bit for romance novels to be more openly sexual - and, as the case sometimes was, for pornographic novels to proliferate.
The lines between outright romance and erotic novels blur quite a bit in the 1980s. The Sleeping Beauty series by Anne Rice (writing as A. N. Roquelaure) were openly erotic BDSM-themed novels, but borrowed strongly from romance novel tropes; Brian McNaughton (writing as Sheena Clayton) wrote a series of novels for Sienna Books which sort of prefigured the paranormal romance novel, combining explicit sexuality and a fantasy/romantic plot and atmosphere. Romance comic books largely declined after the 1970s as the major publishers shifted their interests to the burgeoning genre of superhero comics - but made something of an indie-oriented comeback with titles like Love & Rockets, Strangers in Paradise, and the comic adaptations of Harlequin romance novels.