C'est en 1976 que quatre kids londonien du quartier populaire de Camden Town, l'organiste Mike « Monsieur Barso » Barson, le chanteur et trompettiste Cathal « Chas Smash » Smith, le saxophoniste Lee « El Thommo » Thompson et le guitariste Chris « Chrissy Boy » Foreman, créent une petite formation de ska fortement inspirée par les rythmes rocksteady du chanteur jamaïcan Prince Buster: The Invaders. En 1979, après trois ans de tournées dans les clubs de la capitale britannique, ils sont rejoints par le chanteur Graham « Suggs » McPherson, le bassiste Mark « Bedders » Bedford et le batteur Daniel « Woody » Woodgate et abandonnent leur dénomination originelle pour se choisir une nouvelle identité, inspirée encore une fois, d'une chanson de Prince Buster: Madness.
Clairement situé dans la mouvance ska, bien qu'entièrement composé de blancs, Madness évolue dans le sillage d'autres groupes tels que Bad Manners, The Selecter ou encore The Specials, alors locomotive de la scène ska londonienne, sous le patronage du label Two-Tones, créé par Jerry Dammers. Après une tournée triomphale en première partie de The Specials, qui permettra aux 7 membres de Madness de se faire connaître et reconnaître du grand public, le groupe signe son premier 45 tours « The Prince », un hommage à Prince Buster, à qui il doit son inspiration et son identité. Toutefois, en dépit du succès de la chanson-titre, c'est surtout le morceau de la face B, la version quasi-instrumentale d'un vieux titre de rocksteady des années 60, rebaptisé « One Step Beyond », qui imposera le groupe dans le milieu ska. Aussi festif que non-sensique, « One Step Beyond » deviendra vite l'ingrédient indispensable des soirées pogos de la jeunesse contestataire anglaise et européenne. Jerry Dammers ne s'y trompe d'ailleurs pas et encourage le groupe à mettre ce titre en avant sur l'album éponyme qui sortira en octobre 1979, assorti d'un clip-vidéo tourné avec deux bouts de ficelle dans le salon de coiffure tenu par le père de Suggs, qui imposera également les prémisses de l'identité visuelle de toute l'oeuvre future de Madness. L'album, très vite disque d'or, est un énorme succès commercial, mais qui laisse néanmoins un sale goût dans la bouche des sept nutty boys. En effet, la jeunesse du National Front anglais, gravitant à l'extrême-droite du mouvement skinhead, s'en empare et en en fait l'un de ses morceaux fétiches. Malgré tous les démentis produits, l'image de « groupe pro-raciste » collera longtemps à la peau de Madness. Il faudra plusieurs années, interviews, et une chanson-règlement de comptes: « Don't Quote Me On That », pour clarifier les choses et se débarrasser définitivement de cette sulfureuse réputation. C'est peut-être cette récupération involontaire et malheureuse qui poussera le groupe, tout au long des années 80, à s'impliquer politiquement auprès des mouvements de gauche, lors de concerts de soutien au Parti Travailliste, à Greenpeace, ou encore à l'AAA (Artists Against Apartheid) et à produire quelques chansons « engagées » (« For The Wings of A Dove », « The Sun and The Rain »...), hélas souvent perçues comme des concessions offertes au politiquement correct, que les fans de la première heure n'apprécient guère, auxquelles ils reprochent le manque de folie furieuse des débuts, et le ton bien trop guimauve, résolument indigne du mouvement ska.
Sur la lancée de One Step Beyond, Madness sort l'album Absolutely en 1980, leur premier disque de platine, dont seront extraits les titres « Embarassment » et « Baggy Trousers », suivi, en 1981 de Seven, autre disque d'or, porté par les tubes « Shut Up » et « Grey Day ». Dès 1982, soit quatre ans à peine après la formation du groupe, sort le premier best-of, Complete Madness, qui s'offrira même le luxe de chasser les indéboulonnables Queen des sommets des charts britanniques. 1982 sera également l'année qui, aux yeux des fans, verra sortir le dernier « grand » album du groupe, The Rise and Fall, dont est extrait le mythique « Our house » ainsi que les joyeusement foutraques « House of Fun », « Cardiac Arrest » et « Driving in My Car ». Les tournées se succèdent en Europe et aux Etats-Unis.