Born in Risca, in the coal-mining district of Monmouthshire, he was one of six children of Thomas and Anne Brace. Brace briefly attended school before starting work at the local colliery, aged 12. He later worked at Celynnen and Abercarn collieries He soon involved himself in trade union activities and politics and in 1890 was elected the local agent for the South Wales Miners Association. He was also elected to Monmouthshire County Council.
Brace was an early advocate of a single union for all of Britain's colliers, an issue in which he clashed with William Abraham. Folowing the Welsh coal strike of 1898 the Miner's Association became part of the new South Wales Miners Federation, and Brace was elected its first vice-president. He was later to the union's president from 1912-1915.