Образована 1 января 1990 года (как группа образована в конце 1991 года). Была задумана как "экзотик-поп-дуэт" Сергеем Лемохом и Богданом Титомиром, работавшими в то время на подтанцовках у эстрадного исполнителя Владимира Мальцева. Сергей Лемох в 1988 году окончил Московский институт Советской торговли. Фамилию матери (Лемох) решил взять как более подходящую для сценической деятельности. Дуэт мгновенно стал популярным. Музыканты работали в стиле "клуб кинопутешествий", о чем свидетельствует название их первого альбома "Вокруг света", в который вошли такие песни, как "Лондон, гуд бай", "Париж", "Чио-Чио-Сан". После выпуска двух альбомов вышел сборник лучших песен, который включал один ремикс "Чио-Чио-Сан" и три новых "Чао, бамбино" (на которую был отснят клип), "Is it love" и "Танцы в лазерном дыму". В 1993 году "Кар-Мэн" гастролировал по России. В этом же году Лемох принимал участие в съемках рекламных роликов - сигареты "B.O.Y." и продукция фирмы "Hitec". Принимал участие в телевизионной игре "Марафон 15 - старт", где, к сожалению, Лемох не выиграл (его танцоры не смогли ответить на простейший вопрос и он их всех уволил). Был записан саундтрек к мультфильму "Капитан Пронин". В 1994 году вышли сразу два альбома "Русская массированная звуковая агрессия" и "Live...". Все песни группы написаны Сергеем Лемохом. Многие из них занимали ведущие места в различных хит-парадах: "Angel of love", "Союз-Аполло", "This is Сar-Man", "Hotel California". Большой популярностью пользовались видеоклипы на песни "Чао, бамбино", "Плохие русские" и др. В 1994 году Лемох написал музыку Н. Сенчуковой для песни "Ты не Дон Жуан". Также записал совместно с Ликой, Ладой Дэнс, С.Владимирской, В.Нечитайло, И.Силиверстовым песню "Дети Луны". В период с 1994 по 1996 год "Кар-Мэн" совсем куда-то пропала. Как стало уже известно, с Кар-Мэн был заключен контракт в Германии. В Германии был записан англоязычный альбом "This is Car-Man". В конце 1996 года вышел долгожданный альбом "Твоя сексуальная штучка", который был просто насыщен медленными песнями. В 1996 году команда отмечала свое пятилетие (как сольного проекта Сергея Лемоха), к нему был приурочен выход нового диска "Твоя сексуальная штучка". Группа гастролировала по Германии, США, участвовала в фестивалях "Голос Азии" (1996), "Славянский базар", "Таврийские игры" (1997). После небольшого затишья в 1998 году вышел альбом "Король диско", вся музыка в котором полностью в стиле (классического) "диско". По причине болезни Алексея Лачинова был задержан выпуск клипа на песню "Тацуйте диско" из альбома "Король диска", который появился только где-то в начале 1999 года. Через полтора года, в декабре 1999 года, вышел альбом ремиксов на старые хиты (с 1991 по 1994 год).