In 1957, Starr formed a doo-wop group, The Future Tones, and began his singing career. Starr lived in Detroit, Michigan, in the 1960s and recorded at first for the small record label Ric-Tic, and later for Motown Records after it absorbed Ric-Tic in 1968.
The song which began his career was “Agent Double’O’Soul” (1965), a reference to the James Bond films popular at the time. Other early hits included “Headline News”, “Back Street”, a cover of The Miracles “Way Over There”, and “S.O.S. (Stop Her On Sight)”. He recorded more soul music for the next three years before having an international hit in “25 Miles” (1968), which peaked at #6 in the United States the following year.