Born in Lambeth, England, Sullivan was the elder brother of composer Arthur Sullivan. His father, Thomas Sullivan (1805–1866), was a military bandmaster and music teacher born in Ireland, who was educated in Chelsea, London and was based for some years at the Royal Military Academy Sandhurst. His mother Mary Clementina (née Coghlan, 1811–1882) was English, of Irish and Italian descent. He trained as an architectural draftsman but soon decided on a career as a performer. Later, he quipped, "I still draw large houses." According to Leslie Ayre, Fred sometimes accompanied Arthur to the Chapel Royal and "amuse the boys with comic songs".