On 5 May 1866, at the age of nineteen, Ellis married Milford Shipp, a recently returned missionary of thirty who had lost one wife by death and another by divorce. The Shipps moved to Fillmore where Milford tried to establish a store. After that enterprise failed, the couple returned to Salt Lake City. Two years after his marriage to Ellis, Milford entered the practice of polygamy when he married Margaret Curtis in 1868, Elizabeth Hilstead in 1871, and later Mary Smith.

Ten children were born to Ellis and Milford Shipp, but four of them died in infancy. In October 1873 Brigham Young announced that women would be sent east for training as doctors so that they could return to Utah and serve as physicians. The first one sent, Romania Pratt, enrolled in the Woman's Medical College of Pennsylvania in Philadelphia in the fall of 1874. The following year, Margaret Curtis, Ellis' sister-wife, also enrolled in the Philadelphia school but after a month returned to Utah and her family because of homesickness. (She later returned to complete her degree in 1883.) Ellis willingly took Margaret's place and, with little time for preparation, set out for Philadelphia on 10 November 1875, leaving behind her three small children in the care of her three sister-wives.