Stephen Collins Foster composed “Where Has Lula Gone?” as a companion song to “Lula Is Gone.” It was deposited for copyright on September 7, 1858. A manuscript in the composer’s handwriting can be found at the Library of Congress (ML96.F8). 

According to Evelyn Foster Mornweck’s The Chronicles of Stephen Foster’s Family:

The verses of “Sadly to Mine Heart Appealing” were written by Eliza S. Carey. Robert P. Nevin has stated that Stephen composed the melody for this song in 1839. He dedicated it to Rachel Keller Woods, sister of Mary Keller, that sweet singer of old-time ballads whose death in 1846 affected Stephen and his family so deeply. But Stephen did not publish the song until 1858. During that year, he brought out four other compositions, “Linger in Blissful Repose,” “Lula Is Gone,” “My Loved One and My Own, or Eva,” and “Where Has Lula Gone?” These compositions are all of a sentimental order, and there are no negro melodies amongst them. Stephen was hewing to the line of “refined” composition with a vengeance, and his income suffered accordingly.