In the 1896 close season, Haynes was persuaded to leave the Midlands and move to the south coast to join Southern League Southampton St. Mary's, though Small Heath retained his Football League registration [REF].
In his first season with the "Saints", he converted from a half back to play at left back; his pairing with Samuel Meston helped Southampton to claim their first Southern League title at the end of the 1896-97 season, with only 18 goals conceded from 20 matches [REF].