La madre de Mellberg era profesora de educación física y pasó su amor por el deporte a su hijo.^[1]​ Cuando era joven, Mellberg disfrutaba del tenis y soñaba con jugar en Wimbledon en lugar de la Copa Mundial de Fútbol. Incluso era considerado una especie de prodigio del tenis hasta que a los 14 años se empezó a interesar por el fútbol.^[2]​

Jugó en un club local de Gullspång antes de ser reclutado por el Degerfors IF. Después jugó para el club AIK de la capital sueca en donde causó una buena impresión y fue vendido, solo 10 meses después de haber sido comprado, al club español Racing de Santander. Tardó un poco en acoplarse al fútbol español pero pronto impresionó en su primera temporada, incluso se encuentra en el 11 ideal de toda la historia del club español.^[3]​

El Aston Villa de Inglaterra logró obtener su firma en 2001, y rápidamente se convirtió en un titular constante y vital del equipo.^[4]​ Fue nombrado capitán por el entrenador David O'Leary y fue una parte importante del equipo que terminó sexto en la Premier League y llegó a las semifinales de la Copa de la Liga en la primera temporada de O'Leary. Mellberg renunció como capitán después de la Copa Mundial de Fútbol de 2006, siendo sustituido por Gareth Barry. En 2006, el nuevo entrenador Martin O'Neill continuó considerando a Mellberg como primera opción en la defensa central. En la jornada inaugural de la temporada 2006-07, se convirtió en el primer jugador en anotar un gol oficial en el nuevo estadio del Arsenal, el Emirates Stadium.^[5]​ Durante la temporada 2007-08, jugó en la posición de lateral derecho tras la compra de Zat Knight, quien jugó junto a Martin Laursen en el centro de la defensa.

En enero de 2008 se anunció que Mellberg había firmado un acuerdo con la Juventus de Italia.^[6]​ Su último partido en casa para el Aston Villa fue contra el Wigan Athletic, el 3 de mayo. El juego fue designado como el día "Olof Mellberg" en reconocimiento de su servicio al club. En su último partido con el Aston Villa, de visita ante el West Ham United, Mellberg dio a cada fanático del Villa en Upton Park, una camiseta con su nombre y número en la parte posterior y el mensaje Thanks 4 Your Support (Gracias por su apoyo). También dijo que enmarcaría el kit que utilizó en su último encuentro con el Aston Villa. Es muy respetado por los seguidores del Aston Villa y considerado uno de sus más grandes jugadores de la historia.^[7]​

En julio de 2008 se oficializó su traspaso a la Juventus de Turín donde firmó un contrato por tres años.^[8]​ En su única temporada, como suplente de Giorgio Chiellini y Nicola Legrottaglie, disputó un total de 37 partidos con la camiseta blanquinegra y marcó dos goles.^[9]​

El 23 de junio de 2009 fue transferido al Olympiacos por la suma de 2,5 millones de euros y firmó más tarde un contrato por tres temporadas.^[10]​ A pesar de la rotación de varios entrenadores en el club durante su estancia allí, fue una constante en la defensa central. Al final de la temporada 2011-12, rechazó extender su contrato en busca de un nuevo reto.^[11]​

El 8 de agosto de 2012 fue fichado por el Villarreal C. F., que entonces jugaba en la segunda división española.^[12]​ En su estancia en el club español, disputó 29 encuentros y anotó dos goles, siendo una parte importante del equipo que terminó segundo y ascendió a Primera División.^[13]​

El 9 de julio de 2013 firmó un contrato de dos años con el F. C. Copenhague.^[14]​ El 31 de julio de 2014, anunció en un comunicado de prensa que había rescindido su contrato con el club danés y que su carrera como jugador había terminado.^[15]​

En marzo del 2000 hizo su debut internacional con la selección de Suecia en un amistoso frente a Austria. Durante un entrenamiento abierto del equipo antes del Mundial 2002, se peleó con su compañero de equipo Fredrik Ljungberg, después de cometerle una dura entrada.^[16]​ Asimismo, cuatro años después y según una filtración desde dentro del equipo, tuvieron una discusión muy acalorada después del empate ante Trinidad y Tobago en el Mundial 2006.^[17]​

Durante la Eurocopa 2004, tuvo un papel clave en la defensa sueca. Sin embargo, en el partido decisivo contra Países Bajos, falló su penal en la tanda de penaltis y no pudieron avanzar a las semifinales.^[18]​ Después de la Copa Mundial de la FIFA 2006, renunció a su capitanía y Ljungberg tomó su lugar como capitán del seleccionado europeo.^[19]​ En abril de 2012 anunció que tenía la intención de dejar la selección nacional después de la Eurocopa 2012.^[20]​ En total, participó en 117 ocasiones en las que marcó ocho goles.^[21]​

Inició su carrera como entrenador en el IF Brommapojkarna en noviembre de 2015, firmando un contrato de dos años y asumiendo el cargo tras su reciente descenso a la tercera división del fútbol sueco.^[22]​ En su primera temporada a cargo, obtuvo el ascenso a la Superettan y, en octubre de 2017, logró devolver al club a la Allsvenskan. Al final de la campaña, decidió no renovar su contrato con el club que estaba a punto de expirar.^[23]​

El 1 de julio de 2019 el Fremad Amager anunció que se había unido al club como su nuevo entrenador.^[24]​ Durante su corta estadía, el equipo perdió solamente en tres ocasiones durante los diez partidos que dirigió en Dinamarca.

El 3 de septiembre de 2019 asumió al frente del Helsingborgs IF y firmó un contrato por dos años y medio.^[25]​ Su estancia en el club no fue tan satisfactoria como esperaban, ya que terminó la temporada 2020 en el puesto 15.º, lo que significó el descenso a la Superettan.^[26]​ En diciembre de ese año anunció su salida del equipo sueco.^[27]​

Antes de la temporada 2023, regresó al IF Brommapojkarna,^[28]​ donde se le asignó el puesto de entrenador compartido con Andreas Engelmark.^[29]​ Luego de finalizar en la décima posición, el club anunció su salida del cargo en noviembre de 2024.^[30]​

El 26 de noviembre de 2024 asumió al frente del St. Louis City SC.^[31]​

• Ficha en SvFF
• Que fue de Olof Melberg