Whilst growing up in the Splott district of Cardiff as a young teenager, he required operations on his knees, feet and shoulders. Due to the extent of these operations, a rugby career seemed unlikely. In 1961 he joined the army after leaving school and working for a while as a motor mechanic. He was posted to Catterick in the North Riding of Yorkshire, and while there was picked for an inter-corps rugby match on account of being Welsh. Sullivan chose to play in the match as admitting to having a major injury would have led to being invalided out of the army. His plan was to deliberately play badly to avoid being picked again. However, instinct took over and after scoring a long distance try with no ill effects, he decided to make the most of the army training to further progress his hopes of playing rugby.