The club was formed on 17 May 1904 at Shaddongate United's annual general meeting where the club's members voted to change the team's name to Carlisle United. The newly formed club initially played at Milhome Bank and later at Devonshire Park, finally settling at their current home Brunton Park in 1909.
In 1905, Carlisle United joined the Lancashire Combination but were only admitted after agreeing to pay all visiting teams’ travel expenses for two years, due to Carlisle not being located in Lancashire. After the league reorganised four years later the board at United decided it did not suit the club's best interests to be there any longer and the club entered the North Eastern League in place of their reserve team who had previously played in the league and been a founding member. When the Carlisle United first team left to join the Football League the reserve team resumed its place in the competition. Carlisle United were crowned champions of the North Eastern League in 1922.
The 1927-28 season was Carlisle's last in the North Eastern League. An excellent home record helped them to second in the table finishing a full 10 points behind Champions Sunderland Reserves. The close season meant the usual round of applications to join (and be re-elected to) the Football League. Carlisle went up against Chester City, Durham City (applying for re-election), Nelson and York City. On 4 June 1928 a delegation of representatives from Carlisle United took their seats at the Football League meeting in London to hear the results of the vote. They were cast as follows: Nelson - 37, Carlisle - 33, Durham - 11, York - 7, Chester - 2. The result meant Carlisle would replace Durham City as members of the Football league.