2005 - 2006: Formación y The Disappearance of Adalia EP (2005 - 2006)
Nathan y Matthew Leone aparecieron por primera vez como integrantes de una banda llamada The Blank Theory originaria de Chicago mientras que el baterista Dan Torelli y el guitarrista Mateo Camargo estaban en una banda llamada Reforma, la que se había trasladado a Chicago. Es ahí donde los cuatro integrantes se conocen y, descontentos con su situación en sus respectivas bandas, deciden disolverlas y así unirse y formar Madina Lake. Shawn Currie de The Blank Theory también estaba en la alineación original de Madina Lake, pero decidió abandonar la banda poco después de que comenzaran a trabajar en su primer material. Tuvieron su primer concierto el 21 de mayo de 2005 en el histórico Metro Chicago.[1]
Tuvieron su primer reconocimiento de los medios cuando aparecieron en una edición especial de Twin Fear Factor. Ganaron el premio de 50.000 dólares y lo invirtieron en un proceso de grabación del cual saldría su primer EP titulado The Disappearance of Adalia que fue lanzado el 22 de agosto de 2006.
2006 - 2008: From Them, Through Us, to You
Después de lanzar The Disappearance of Adalia la banda ganó un contrato de grabación y firmó con Roadrunner Records en abril de 2006. Su primer álbum se titula From Them, Trought Us, to You y fue lanzado el 27 de marzo de 2007. Fue producido y mezcaldo por Mark Trombino. El álbum debutó en el #154 del Billboard 200 en los Estados Unidos y en el #60 en el UK Albums Chart del Reino Unido. Tras la publicación del álbum la banda inició un tour junto con Fightstar además de participar en el Projekt Revolution. Inicialmente iban a participar en Warped Tour de 2007, pero se decidieron por el Stage Revolution, debido a que Linkin Park los había escogido.[2] Madina Lake también ha viajado junto con bandas como Story of the Year, Aiden y Mayday Parade entre otros.
Durante 2007 fueron premiados por la revista británica Kerrang! como Mejor Artista Revelación Internacional.[3]
Un DVD que relata el proceso de composición y grabación de From Them, Trought Us, to You, así como viajes y eventos que le siguieron fue lanzado a finales de 2008.[4]
2009 - Presente: Attics to Eden
La banda grabó su segundo álbum de estudio que lleva por nombre Attics to Eden. Fue producido por David Bendeth y publicado el 5 de mayo de 2009. Para comenzar la gira de promoción del álbum, la banda acompañó a Anberlin en su gira canadiense.[5] Posteriormente participaron en el Soundwave festival del 21 de febrero al 2 de marzo, además de presentarse en todas las fechas del Warped Tour de 2009.[6][7][8] La banda recorrió el Reino Unido en marzo y abril de 2010, con el apoyo de We Are The Ocean y Mayday Parade.[9] En mayo de 2010 anunciaron a través de una entrevista con Rocksound que habían dejado su sello discográfico, Roadrunner.