Logo depois de ter voltado da sua tradicional viagem à Barbados, Melanie estava namorando um homem até então desconhecido... tempos depois seu nome foi divulgado: Thomas Starr, um inglês, chefe de construtora em Hetfordshire.

Os trabalhos para o segundo álbum solo já haviam começado, e Melanie foi fotografada várias vezes por Los Angeles.

Em março ela foi para o casamento de Liza Minnelli e David Guest, acompanhada pelo novo namorado, Tom (Thomas Starr).

Rumores surgiram de que Mel cantaria a música da Copa do Mundo, "Who Invented Fish And Chip (Pop It In The Onion Bag)", coisa que não aconteceu.

Desde de março de 2002, surgiram rumores de que uma das músicas do novo álbum se chamaria Here It Comes Again.

Em abril, foi lançada a trilha sonora e o filme Driblando o Destino (Bend It Like Beckham), com a nova versão da música Independence Day de Mel, não-lançada anteriormente, mas já conhecida pelos fãs, por ser cantada nos shows. Mel compareceu à premiere do filme, que em uma das cenas também usou a música I Turn To You.

Infelizmente, dia 25 de abril, Lisa Left-Eye Lopes, integrante do TLC que cantou em Never Be The Same Again, veio a falecer em um acidente de carro em Honduras, onde passava férias.

Melanie participou da re-abertura do centro de medicina alternativa Women & Health em junho, aparecendo lá para uma sessão de fotos.

Vários supostos nomes de músicas que estariam no segundo álbum solo começaram a aparecer na imprensa. Rumores surgiram de que a demora do lançamento era porque a gravadora, Virgin Records, queria que Melanie perdesse peso antes de começar a divulgar o novo álbum. Tudo foi desmentido por Melanie no seu site oficial, que disse que a gravadora não tinha nada a ver com sua vontade própria de perder peso: "Eu não assinei contrato com uma agência de modelos, que m***da."

Melanie aparece sem o dente de ouro (a capinha de ouro que cobria seu dente da frente) em outubro, na festa de lançamento do Playstation 2, convidada por Guy Oseary.

Rumores de que Melanie ia recorrer a cirurgia à laser para remover as tatuagens, apareceram e logo foram desmentidos.

Dia 12 de novembro, o título do álbum foi divulgado pelo site oficial: Reason! E foram confirmados os rumores de que a música Help Me Help You de Holy Valance tinha sido escrita por Mel, e de que Here It Comes Again seria o primeiro single de Reason.

Em 14 de novembro, Mel compareceu ao MTV Europe Music Awards em Barcelona, Espanha, para entregar à Pink o prêmio de melhor canção junto com a cantora Anastacia.

Em entrevistas, Mel admitiu que quando estava em depressão, pensou em abandonar a carreira, mas logo percebeu que a música era a sua razão e por isso deu este título ao álbum, Reason.

Logo no começo de dezembro, começaram a aparecer fotos do making off do clipe Here It Comes Again. Foram anunciadas também as datas de lançamento do álbum e single, pelo site oficial.

2003 já começou agitado: Melanie e Tom foram para o The Circle Club em Manchester com 9 amigos no dia do aniversário de 29 anos de Mel. Thomas foi pegar a bolsa de Melanie e acabou pegando a de uma outra mulher que estava no clube. Ele foi acusado de supostamente tentar roubá-la, e a mulher fez um escândalo mandando chamar os seguranças, que levaram Thomas arrastado para fora do clube e o jogaram no meio da rua. Melanie saiu correndo atrás, driblando os paparazzi. Os dois pegaram carona no carro de um dos amigos e foram embora para casa.

Em janeiro o novo site oficial foi lançado, uma entrevista exclusiva sobre o lançamento do novo álbum foi disponibilizada, juntamente com um webchat.

As Spice Girls voltam a se reunir em fevereiro. Victoria faz um jantar em sua casa para reunir todas as garotas, inclusive Geri Halliwell. A imprensa especulou que o resultado da conversa seria uma nova turnê ou o lançamento de uma coletânea de músicas. Mas a conversa não gerou novos planos profissionais para o grupo.

Here It Comes Again, o primeiro single do segundo álbum solo, Reason, é lançado em 24 de fevereiro.

Com a entrada em 7º lugar de Here It Comes Again nos charts, começaram a aparecer rumores de que a gravadora Virgin Records estava começando a ficar insatisfeita com Melanie. A informação foi desmentida pela empresária de Mel, Nancy Phillips.

O segundo álbum solo, Reason é lançado em 10 de março, e vem com dedicatória para Tom: "Eu dedico esse álbum para você... você é a minha verdadeira inspiração. Eu te amo. - Melanie".

A turnê pelo Reino Unido e Irlanda começou em abril e fez muito sucesso.

Em maio, o show de Shepherd's Bush Empire foi transmitido ao vivo pela versão em 3D do site oficial.

Também em maio, o artista britânico Peter Blake atualizou a colagem da lendária capa do disco dos Beatles, Sgt. Pepper's Lonely Hearts Club Band. John Lennon, Paul McCartney, George Harrison e Ringo Starr continuam na capa, mas o grupo de ícones do século 20 que os cerca foi substituído por uma série de figuras mais recentes e relacionadas mais intimamente com Liverpool. Entre eles Melanie C, o futebolista Mark Owen e o ex-primeiro ministro britânico Harold Wilson. Essa nova colagem foi encomendada pela galeria Tate, como parte da campanha de Liverpool para se tornar a Capital Européia da Cultura.

Em junho, Louis Walsh e Mel C discutiram ao vivo no programa CD:UK. Tudo começou quando os dois foram sentados um perto do outro para o que viria a ser uma tranqüila discussão sobre os novos clipes musicais. Mas depois de Mel falar sobre suas visões negativas a respeito dos Westlife, ficou claro que ela havia comprado uma briga com Louis, o empresário do grupo. Louis de repente começou a defender os garotos, dizendo que eles são a banda de garotos de mais sucesso de todos os tempos, chamando Mel e o resto de suas companheiras de "fracassadas".

Dia 2 de junho, o single On The Horizon é lançado. Os fãs reclamam que o single estava sofrendo problemas de distribuição pela Virgin Records, pois quando o single era encontrado em alguma loja, era em pouca quantidade.

Com On The Horizon em 14º lugar, os rumores de que Mel seria brevemente despedida da Virgin tomaram força.

Melanie começa a declarar que está insatisfeira com a gravadora, por não promove direito nem o álbum, nem os singles.

A música Let's Love é escolhida pela Toyota para tocar durante a propaganda do novo carro no Japão. Um single especial japonês não-comercial é lançado com a música, no dia 6 de agosto.

Melanie já estava gravando o clipe para o próximo single, Yeh Yeh Yeh, quando recebeu um convite para participar de um reality show de esportes chamado The Games. O objetivo do programa era de mostrar uma competição de esportes entre celebridades, recebendo votos dos telespectadores via telefone, o que arrecadava dinheiro para as instituições representadas pelas celebridades. Com o convite aceito, Melanie foi para Sheffield na casa feita especialmente para o programa, onde as celebridades iriam morar durante uma semana.

Em agosto, os treinos para as competições de esporte no The Games começaram, sob as orientações do treinador das Olimpíadas.

Durante os treinos para a prova de patinação no gelo, Melanie bateu a cabeça numa parede de acrílico. Um fotógrafo disse: "Ela é muito ruim no gelo. Ela foi de cara numa tela de acrílico ao lado do rinque de gelo. Ela bateu o nariz e chegou até a reclamar da dor."

O programa começou no dia 8 de setembro.

No dia 11 de setembro, durante uma luta de judô com a Miss Mundo Azra Akin, Melanie levou uma queda, rompendo 3 ligamentos do seu joelho direito. Ela foi levada em urgência para o hospital e precisou de cirurgia para reconstruir seus ligamentos com tendão, metal, parafusos e grampos. Ela ficou algumas semanas sem poder andar e teve que usar um aparelho (uma tala com dobradiças) na perna por um tempo.

No último dia do The Games, os participantes fazem uma homenagem para Mel, todos vestidos com camisas escritas "Nós te amamos Mel". Harvey, que foi o primeiro colocado dos homens, disse que iria comprar 30 cópias do single Yeh Yeh Yeh quando este fosse lançado!

Com tudo isso, o single foi adiado várias vezes e até virou um duplo a-side com a inclusão da balada Melt, uma música mais calma para possibilitar a divulgação de Melanie sem precisar se movimentar muito nos palcos de programas de televisão.

O resultado de Melt/ Yeh Yeh Yeh (lançado finalmento no dia 10 de novembro) nos charts foi o pior de toda a carreira de Melanie, ficando em 27º na primeira semana de lançamento. O single tinha sido pouco divulgado, só com algumas apresentações de Mel na TV.

Mais rumores de que Mel seria despedida da Virgin Records apareceram na imprensa.

Melanie vai para a casa da mãe, em Liverpool, para se recuperar do acidente e os tablóides publicam rumores de que ela teria que ficar 18 meses sem andar! Logo Mel foi ao programa GMTV e esclareceu que em breve voltaria a trabalhar.

A turnê alemã de fim-de-ano, "On A Mission", foi cancelada e Melanie só conseguiu fazer poucas apresentações usando a tala que imobilizava sua perna.

Em novembro de 2003 começaram a aparecer notícias sobre a insatisfação de Melanie com a gravadora Virgin Records, alegando que a gravadora não estava interessada na música, só nas vendas.

Em dezembro, Mel começa a fazer algumas aparições sem a tala na perna, em outras, continua usando-a. Ela faz dois shows de fim-de-ano: um em Londres e outro em Liverpool.

Dia 30 de dezembro, a saída de Melanie da gravadora Virgin Records é oficialmente anunciada. O porta-voz disse: "É verdade, Melanie não está mais na Virgin Records, mas foi uma separação amigável. Ela já está trabalhando num novo material que esperamos para ser lançado no próximo ano (2004). Sobre assinar um novo contrato com uma gravadora, eu posso confirmar que ela não vai aceitar o primeiro contrato oferecido - ela vai ter cautela. Ela está muito feliz no momento e otimista sobre seu futuro e carreira."