Nuijamiehet oli kitaristi Kalle Kaliman sekä saksofonisti Mikko Innasen kehittelemä kvartetti, joka syntyi miesten Sibelius-Akatemian opiskeluvuosina, vuonna 1996. Yhtyeen basistina toimi nuori lahjakkuus Lasse Lindgren ja rumpalina moneen taipuva Mika Kallio.

Yhtyeen ohjelmisto muodostui pääasiassa perustajakaksikon sävellyksistä, joiden tyyliskaala sijoittui jazzin valtavirran vapaammalle puolelle: rosoista ja särmikästä, mutta vastapainona myös herkkää ja hiljaista ilmaisua. Bändi teki Ylelle kaksi radionauhaa, joista jälkimmäinen eli vuoden 1999 sessio julkaistiin debyyttialbumina Nuijamiehet (Fiasko Records 2000). Levy sai hyviä arvioita, joissa korostettiin sitä, miten persoonallinen yhtyeen soundi kaikessa monimuotoisuudessaan on.

Vaikka kollegoilta satelikin paljon kannustavaa palautetta, oli Nuijamiesten tyyppiselle yhtyeelle vuosituhannen vaihteessa kuitenkin hankala löytää keikkoja. Kalle Kaliman muutettua Berliiniin syksyllä 2000, jäivät kitaristin kotimaiset yhtyeet jäihin, Nuijamiehet mukaan lukien.

Yleisön kannalta Nuijamiehet oli virkistävä ja persoonallinen bändi: yksi esimerkki siitä, että suomalainen jazz alkoi rikastua myös vapaampaa ilmaisua käyttävillä nuorilla muusikoilla. Nuijamiehet olivat myös vuoden 2000 kiertueellaan ensimmäinen nuorempien kotimaisten jazzmuusikoiden muodostama yhtye, jonka Charles Gil valitsi mukaan Vapaat äänet -kiertueelleen.