Milne was a successful right-half for Liverpool during the 1960s and played a prominent role in Liverpool's rise from the old Second Division, forming a partnership with Gerry Byrne. While at Anfield, he won First Division Championship medals in 1963–64 and 1965–66, a Second Division Championship medal in 1961–62 and two shared Charity Shield triumphs in 1964 and 1965.
Milne missed the 1965 F.A.Cup triumph in 1965 through injury, but played a major role just a few days later as the Reds entertained Inter Milan in the first leg of the European Cup semi final. Bill Shankly sent out the injured pair Milne and Gerry Byrne to parade the F.A Cup before the kick-off. The Reds went on to win the match 3–1 but were beaten 3–0 in the return leg.
Milne was selected to represent England at wing-half 14 times making his debut for Alf Ramsey's team in a prestigious friendly with Brazil at Wembley in a game that took place on 8 May 1963 and finished one-all.
Milne also became the part-time manager of the England Youth team in 1972, helping them to win the European Youth Championship that year.
Milne joined Joe Mercer at Coventry City as team manager in June 1972, taking full control in 1974, upon Mercer's elevation to the Board. He was shortlisted for the England management role following the departure of Sir Alf Ramsey, but was overlooked in favour of Don Revie. He continued at Coventry until 1981, producing several exciting teams and securing the club's First Division status. The 1977–78 season saw Coventry's most exciting top-flight team. Gordon Milne settled on an attacking 4–2–4 formation. A side containing Tommy Hutchison, Mick Ferguson, Ian Wallace, Terry Yorath, Graham Oakey, Bobby MacDonald and Jim Blyth played attacking football that swept many teams aside, often by large margins of victory.
Milne became boss at Leicester City in August 1982, winning promotion in 1982–83 and staying until 1986. He managed Beşiktaş in Turkey for seven years(1987–1994) (where he won three successive titles, during the early 1990s). He has succeeded in creating one of the most successful periods in the history of Beşiktaş J.K. and is still a legend for the Beşiktaş fans. He also managed Nagoya Grampus Eight in Japan before returning to Turkey to take charge of Bursaspor (1996–1997) and then Trabzonspor (1998–1999).