Bracewell started his football career with Stoke City progressing through the youth ranks at the Victoria Ground and made his professional debut against away at Wolverhampton Wanderers just before his 18th birthday. He soon became a regular in the first team and went on to complete three full seasons before in June 1983 he moved to Sunderland for a fee of £250,000 linking up with Alan Durban. He made 141 appearances for Stoke scoring six goals.
Sunderland had an unsuccessful 1983–84 season and Durban was sacked by the Roker Park club and new manager Len Ashurst did not believe Bracewell could play for him and so sold him to Everton for £425,000. It was at Goodison Park where Bracewell enjoyed the most successful spell of his career. As part of a midfield that included Peter Reid, Kevin Sheedy and Trevor Steven, they won two league titles and also enjoyed success in Europe when they lifted the European Cup Winners Cup. Such form prompted a call-up to the full England squad where he went on to win three caps but missed out on a place in Bobby Robson’s 1986 World Cup squad with a broken leg. Paul also played in four losing FA Cup Finals, the last of which came following his return to Sunderland in 1992.
He left Sunderland for the second time to join arch rivals Newcastle United but returned to Wearside in 1995 and helped Sunderland gain promotion to the Premier League. Unable to keep down a place in the years that followed, Bracewell reunited with his former Newcastle manager Kevin Keegan at Fulham in 1997. He retired from playing football in 1999 to take up a Managerial role at Fulham.
In September 1997, Bracewell took a similar role with ambitious Division Two club Fulham, working under head coach Ray Wilkins and director of football Kevin Keegan. When Wilkins was dismissed at the end of the season, Keegan took sole charge of the first team and kept Bracewell as his assistant. Keegan accepted the offer to become England national football team manager in March 1999, but remained in charge of the Fulham team until the end of that season, guiding them to the Division Two title with 101 points, before quitting as Fulham manager. Bracewell was promoted to the position of manager, and despite them competing in the top half of Division One throughout the campaign, he was dismissed on 30 March 2000 in favour of the more experienced Jean Tigana, who achieved promotion to the Premier League a year later. He scored once during his spell with Fulham in a 2-0 win against Wycombe Wanderers in September 1998.
In October 2000 he became manager of Halifax Town although his stint there lasted less than a year. He resigned from the club 4 games into the 2001/02 season. During his brief spell in charge he steered to the team to just 11 wins in 41 games, which included a 2–0 home FA cup exit at the hands of non league Gateshead.