First Nations and Métis people had lived in the area well before the arrival of European families who began settling around Starbuck by 1870. In 1881 the railway came through and in 1885 the community was named Starbuck by the contractor who graded the railway roadbed. According to Geographical Names of Manitoba, the contractor's name was either Vanderstice, Vanderslie, or Vanzile. Also, it may be that Starbuck was named after Starbuck, Minnesota or a similarly named town in Germany. The Post Office was opened in 1887.