Pakistan Navy first entered the competitive tournament in 1984, when they participated in 1984 Inter-provincial Championship. They reached the final of 1999 National Football Championship, losing 4–3 on penalties to Allied Bank. In 2000 National Football Championship Pakistan Navy reached the semi-finals, although the match was abandoned after Pakistan Navy refused to continue the match after receiving a red card and match was awarded in the favor of their opponents Habib Bank. In 2002, Pakistan Navy reached the quarter-finals of 2002 Pakistan PFF's President Cup, they were knocked out by Karachi Electric Supply Corporation after losing 1–0. They reached the 2003 National Football Challenge Cup, losing to Habib Bank 4–2 on penalties after the match ended 1–1, they also reached the 2003 PFF President's Cup semi-finals, where they lost 3–0 to Karachi Port Trust. Pakistan Navy and Pakistan Army competed for "Inter-services Championship" as Pakistan Navy lost 6–1 to Pakistan Army.
Pakistan Navy were the founding members of newly formed Pakistan Premier League. They finished 6th in the league in 2004–05 season. They record some of the biggest victories in the season, defeating Young XI DIK and Mardan 8–1 and 10–0 respectively. In the second season, Pakistan Navy survived relegation by one point, ending the season with 21 points, on 5 October they suffered their biggest defeat in the league, when they lost 5–0 to National Bank. Pakistan Navy won their first silverware in 2008, winning the 2008 National Football Challenge Cup, defeating Khan Research Laboratories 3–1 in the finals. In the 2008–09 season, they failed to defend the National Football Challenge Cup as they lost to previous season's finalist, Khan Research Laboratories 2–1 in the semi-finals, although they won bronze medal after defeating WAPDA 4–3 on penalties in the third-place match of the 2009 National Football Challenge Cup. In the 2009–10 season Pakistan Navy got their highest ever position in Pakistan Premier League, finishing in 4th position with 57 points. They reached the finals of 2010 National Football Challenge Cup, where they lost 4–0 to defending champions Khan Research Laboratories. In 2011–12 season, the club the semi-finals of 2012 KPT Challenge Cup, where they once again lost 1–0 to Khan Research Laboratories, they lost the third-place match to WAPDA on penalties. The club got relegated in 2013–14 season, when Pakistan Football Federation decided to reduce the teams from 16 to 12 for the 2014–15 Pakistan Premier League, Pakistan Navy were the joint-highest placed team in the relegation zone with Habib Bank, sharing 35 points each. Pakistan Navy were knocked out of the group stage in the 2014 National Football Challenge Cup.
Second division
After getting relegated in the 2013–14 season, they competed in the second division, Pakistan Football Federation League. Pakistan Navy defeated Falcon Company and Pakistan Steel 2–1 and 3–1 respectively in group stages and finished top in their group. In the second phase, they again topped their group after defeating Pakistan Television and Sui Southern Gas 5–0 and 1–0 respectively. Pakistan Navy faced Higher Education Commission in the finals of departmental leg, winning 2–1 and earning promotion back to Pakistan Premier League in their first season of getting relegation. They faced Baloch Nushki in the finals of second division, which they won 1–0 and were crowned the champions of second division.
Return to top-flight: 2015–present
After winning the 2014-15 Pakistan Football Federation League, Pakistan Navy were to play in the 2015–16 Pakistan Premier League but no league was held in the country until the current edition in 2018–19. They competed in the National Football Challenge Cup as it was the top-tier of Pakistani football in the absence of the Pakistan Premier League. They competed in the 2015 and 2016, reaching quarter-finals of the former and were knocked out at the group stage in the latter one. Domestic football returned to Pakistan in 2018–19. Pakistan Navy participated in the 2018 National Challenge Cup, reaching quarter-finals where they lost 2–0 to WAPDA. In 2018–19 Pakistan Premier League, they finished 9th in the league, during the season the club recorded one of the biggest scoring and home victory when they defeated Baloch Nushki 6–1.
