The club was formed as Denaby Parish Church, and it was not long after the club was formed in 1895 that they gained a reputation as one of the biggest success stories in local football circles. Within five years of formation Denaby had already won the South Yorkshire League three times (having changed their name to Denaby United in 1898), in their debut FA Cup campaign in 1899 they reached the 3rd Qualifying Round, only losing to Hunslet after a second replay at Oakwell.