Los padres de Mills se conocieron y se casaron en la India británica cuando su padre servía en el ejército británico. Regresaron a Gran Bretaña poco después del nacimiento de Gordon.^[2]​ Hijo único, su madre, Lorna, le enseñó a tocar la armónica. A los 15 años, Mills se unió a un grupo que tocaba en pubs y clubes en los valles del sur de Gales . A los 17 años, realizó el servicio militar y sirvió en Alemania y en la Federación Malaya .^[2]​ Al regresar al Reino Unido, compitió en un campeonato de armónica organizado por Hohner en el Royal Albert Hall de Londres. Quedó segundo, lo que lo clasificó para representar al Reino Unido en la final europea que luego ganó. Invitado a unirse a Morton Fraser Harmonica Gang, conoció a los músicos Don Paul y Ronnie Wells con quienes formó un trío conocido como The Viscounts.^[2]​ El tema "Who Put the Bomp (In the Bomp, Bomp, Bomp)" (1961) se convirtió en un éxito menor en la lista de sencillos del Reino Unido. Su versión de " Short'nin' Bread " (1960) también tuvo éxito.^[6]​

En 1963. su composición, "I'll Never Get Over You", grabada por Johnny Kidd & the Pirates, alcanzando el número 4 en el Reino Unido.^[2]​^[7]​ En el espacio de un año escribió tres éxitos más "Hungry for Love", "Jealous Girl" y "Three Little Words". " I'm the Lonely One " le dio a Cliff Richard and the Shadows un éxito top 10 en 1964.^[8]​

En una fiesta ofrecida por el cantante Terry Dene, Mills conoció a la modelo Jo Waring y se casaron dos años después.^[4]​ Su hija Clair, que entonces tenía tres años, se convirtió en el tema de inspiración de la canción de 1972 "Clair" de Gilbert O'Sullivan .^[9]​

Al ver una actuación de Tommy Scott, una noche en Cwmtillery, se fijó en un nuevo cantante joven llamado Tom Woodward. Mills finalmente se convirtió en mánager de Woodward, a quien rebautizó como "Tom Jones".

El primer sencillo de Jones, "Chills and Fever", originalmente grabado con Joe Meek, fue lanzado a finales de 1964, pero no tuvo éxito. El segundo intento de Jones fue una canción rechazada por Sandie Shaw. La canción fue "It's Not Unusual" que lo impulsó a lo más alto de la lista.^[2]​^[10]​ Mills entonces quiso en un principio que Jones grabara bandas sonoras para películas pero, después del relativo fracaso del tema musical de James Bond "Thunderball",^[10]​ desechó la idea.

Mills rediseñó la imagen del cantante como crooner . Jones también comenzó a cantar material que atrajo a una audiencia más amplia, como el gran éxito country "Green, Green Grass of Home". La estrategia funcionó y Jones volvió a la cima de las listas en el Reino Unido y comenzó a llegar al Top 40 nuevamente en los Estados Unidos. Durante el resto de la década, anotó numerosos éxitos a ambos lados del Atlántico.^[11]​^[12]​^[13]​ En 1967, Jones actuó en Las Vegas por primera vez, en el Flamingo.^[14]​

En 1965, Mills comenzó a trabajar con Gerry Dorsey, un cantante que llevaba mucho tiempo sin grandes éxitos, cambió su nombre a Engelbert Humperdinck y con la exposición televisiva un domingo por la noche de 1967 en el London Palladium, nació una nueva estrella. Entre 1967 y 1972, Mills tuvo bajo su control a dos de las más grandes estrellas de la industria de la música y contrató a la cantante y compositora Lynsey de Paul, que acababa de conseguir un gran éxito con Sugar Me aunque poco después se rompió la relación entre ellos. Como se reveló en su autobiografía de 2015, Tom Jones declaró: "Teníamos a Lynsey de Paul, una gran estrella, aunque se peleó con Gordon (Mills) por querer producir sus propios discos".^[15]​

Mills cambió inteligentemente el nombre de varios cantantes famosos. Tom Woodward se convirtió en "Tom Jones" después de una sugerencia de Godfrey y Glastonbury, quienes se habían opuesto al plan de Decca de llamarlo "Scotty" en 1965. Mills dio a otras estrellas de la música pop sus nombres artísticos, como Engelbert Humperdinck y Gilbert O'Sullivan.^[2]​ Sin embargo, en 1973, las ventas de discos de Jones y Humperdinck habían caído drásticamente, pero Mills había encontrado nuevos talentos con Gilbert O'Sullivan, quien mantuvo el negocio de MAM Records en auge. Mills también produjo los primeros cuatro álbumes de O'Sullivan, generando éxitos notables como "Alone Again (Naturally)", "Clair" y "Get Down". Sin embargo, cuando su éxito comenzó a desvanecerse, no hubo reemplazo. En 1978, Jones se vio reducido a hacer álbumes de música country para el mercado exclusivo de Estados Unidos. MAM se fusionó con Chrysalis Records en 1985.^[16]​

Las cosas se pusieron más feas cuando O'Sullivan descubrió que su contrato discográfico con MAM Records favorecía en gran medida al dueño del sello. O'Sullivan demandó a su ex gerente por sospecha de que este último había "maquillado los libros", al no pagarle a O'Sullivan todas las regalías debidamente ganadas. También se reveló que la excompañera de sello Lynsey de Paul ganó una tasa de regalías del 8%, un 3% más alta que O'Sullivan.^[17]​ Siguió una demanda, con una discusión prolongada sobre cuánto dinero habían ganado sus canciones y cuánto de ese dinero había recibido en realidad.^[18]​ Finalmente, en mayo de 1982, el tribunal falló a favor de O'Sullivan y lo describió como un "hombre evidentemente honesto y decente", que no había recibido una proporción justa de los vastos ingresos que habían generado sus canciones.^[18]​ Se le concedieron 7 millones de libras en daños.

Mills murió de cáncer de estómago en 1986, a la edad de 51 años y está enterrado en el cementerio de Burvale, Hersham .

• "A Little You"^[19]​ (1965) (Freddie and the Dreamers);^[20]​ (Tom Jones)^[21]​
• "And I Tell The Sea"^[22]​ (1965) (Tom Jones)
• "Hide and Seek"^[23]​ (1966) (Tom Jones)
• "High Time"^[24]​ (1966) (Paul Jones)^[25]​
• "Hungry for Love"^[26]​ (The Searchers), (Johnny Kidd & the Pirates)^[7]​
• "If I Had You"^[27]​ (1966) (Tom Jones)
• "I Like The Look of You"^[28]​ (1964) (The Fortunes)
• "I'll Never Get Over You"^[29]​ (1963) (Johnny Kidd & the Pirates)^[7]​
• "I'll Never Let You Go"^[30]​ (1967) (Tom Jones)
• "I'm the Lonely One"^[31]​ (Cliff Richard, 1964);^[8]​ retitulada "The Lonely One" (Tom Jones, 1967)^[32]​
• "I've Got a Heart"^[22]​ (1966) (Tom Jones)
• "It Takes a Worried Man"^[33]​ (1965) (Tom Jones)
• "It's Not Unusual"^[5]​
• "Key to My Heart"^[21]​ (1966) (Tom Jones)
• "Lady Godiva"^[34]​ (1966) (Peter and Gordon)^[35]​
• "Little by Little"^[22]​ (1966) (Tom Jones)
• "Not Responsible"^[36]​ (1966) (Tom Jones)^[10]​
• "Once Upon a Time"^[33]​ (1965) (Tom Jones)
• "Pretty Ribbons"^[37]​ (1968) (Engelbert Humperdinck)
• "Smile Away Your Blues"^[38]​ (1968) (Tom Jones)
• "Some Other Guy"^[39]​ (1965) (Tom Jones)
• "Take My Heart"^[40]​ (1966) (Engelbert Humperdinck)
• "Ten Guitars"^[41]​ (1966) (Engelbert Humperdinck)
• "The Rose"^[22]​ (1965) (Tom Jones)
• "Things I Wanna Do"^[42]​ (1967) (Tom Jones)
• "Three Little Words (I Love You)"^[43]​ (1964) (The Applejacks)^[44]​
• "Untrue Unfaithful"^[22]​ (1965) (Tom Jones)
• "Where Do You Belong"^[21]​ (1966) (Tom Jones)