Before settling into the current forum of music collaboration, Yuka Honda and Miho Hatori formed a loose punk jam band know as "Leitoh Lychee". While hanging out writing music or after a night's gig, they often wandered over to one of the many great New York restaurants to relax, talk, and enjoy the food. Out of these late-night snacking sessions came several song concepts and finally, the band Cibo Matto itself.

Cibo Matto recorded their first mini CD on the Japanese recording label, "Error Records" . The self-titled mini album "Cibo Matto", was released in Japan in 1995. The CD included material already prepared in the United States for demos and their two independent 7" singles. The hard work that Yuka and Miho had put in over the years came together in the release of the CD, "Viva! La Woman", in early 1996. With the distribution resources of Warner Brothers Records behind them, Cibo Matto found a great deal of new success and popularity. Their second release on Warner Brothers was the mini CD titled, "Super Relax", in 1997.

Sean Lennon joined Miho and Yuka in the studio to provide the bass on most of the tracks for the "Super Relax" album. After the release of Super Relax, Cibo Matto went back to playing live gigs. They started taking Sean along on tour to accompany them on bass guitar. Over time, Sean came to be recognized as a member of what had previously been a two person band.

In addition to Sean on bass, Cibo Matto enlisted Timo Ellis to play drums and help out on vocals while touring. When it came time to start recording their third major release in 1998, "Stereotype A", Timo was there. They went into the studio as a four piece band, but by the end of the sessions another full time member, Duma Love, had been added to the band's bill. Duma plays electric drums, percussion, and raps. Duma can be heard on "Stereotype A" doing the impressive rap on "Lint Of Love" and the human beat box on "Clouds".

The band, in its current incarnation now has five main members, Yuka Honda, Miho Hatori, Timo Ellis, Sean Lennon, and Duma Love; with special guest appearances by their network of musical associates and friends, including guitarist Marc Ribot, John Medeski and Billy Martin of Medeski, Martin & Wood, Soul Coughing's Sebastian Steinberg, Buffalo Daughter's Zak and Yumiko Ohno. Each member shares a common interest in the cooperative development of new musical ideas.

Their latest, Stereo Type A is a broadly ambitious pop album. "You can take a hardcore Indian phrase, set it to a hip-hop beat, have country guitar in the back, and make it work," says Yuka. "I really think that technology, if we think about it positively, can give us a brighter future. One where stereotypes will be obsolete."