On September 18, 1892, he formed a West Virginia Grand Lodge of the Knights of Pythias, one of the leading secret black fraternal orders of the day. The organization included representatives from lodges at Raymond City, Huntington, Charleston, and Montgomery. The black Knights of Pythias was an important social organization for African Americans. Dr. Ancella Bickley writes, "It and other secret orders enhanced the sense of community and national connection among blacks, providing them with opportunities to share in business, social, and civil activities under the lodge's aegis." (James D. Randall and Anna E. Gilmer, Black Past, 17) Starks was grand chancellor of the state organization from the time of its inception. He became the national vice chancellor in 1897 and national supreme chancellor in 1901. The order's national membership grew from 9,000 to 146,869 under Starks' leadership as supreme chancellor.
The importance of southern West Virginia's African-American vote increased as the region's black population grew in the 1890s and early 1900s. Politicans turned to various black civic leaders to organize voters. In Charleston, Samuel Starks, along with barber James Hazelwood and lawyer Phil Waters, became significant players in the Republican party. For his efforts, Starks was named state librarian by Governor A. B. White in 1901 and was reappointed by Governor William M. O. Dawson in 1905.
Starks died of peritonitis on a Charleston operating table on April 3, 1908, at the age of forty-two. Many black-owned businesses closed in his honor. Starks' funeral was attended by thousands and speeches were given by Governor Dawson and West Virginia Colored Institute President J. McHenry Jones. In 1911, the Knights of Pythias placed a thirty-two-foot monument on his grave in Charleston's Spring Hill Cemetery. Starks' home on Shrewsbury Street is listed on the National Register of Historic Places.