Образована 1 января 1990 года (как группа образована в конце 1991 года). Была задумана как "экзотик-поп-дуэт" Сергеем Лемохом и Богданом Титомиром, работавшими в то время на подтанцовках у эстрадного исполнителя Владимира Мальцева. Сергей Лемох в 1988 году окончил Московский институт Советской торговли. Фамилию матери (Лемох) решил взять как более подходящую для сценической деятельности. Дуэт мгновенно стал популярным. Музыканты работали в стиле "клуб кинопутешествий", о чем свидетельствует название их первого альбома "Вокруг света", в который вошли такие песни, как "Лондон, гуд бай", "Париж", "Чио-Чио-Сан".
В самом начале 1991 года "Кар-Мэн" отметил годовщину своего существования, а в апреле 1991 года экзотик-поп дуэт "Кар-Мэн" распался. Сергей Лемох, сохранив за собой права на название и набрав музыкантов, группу танцоров, продолжал эксперименты в стиле "экзотик-поп", а Богдан Титомир подвивал основу популярной музыки, внедряя движение "High Energy". Уже без Титомира вышел второй альбом под названием "Кар-Мания". На заглавную тему "Bad russians" был отснят клип. "Кар-Мэн" завоевала первые места на конкурсах "Шлягер-90", "50х50" (1991), "Звездный дождь" (1991). В том же 1991 была удоcтоена национальной премии "Овация" в номинации "поп-группа". В 1991 году Лемох написал музыку для нескольких песен Н. Гулькиной - "Китай", "Надо лишь мечтать", "Айвенго", "Прощай навек".
После выпуска двух альбомов вышел сборник лучших песен, который включал один ремикс "Чио-Чио-Сан" и три новых "Чао, бамбино" (на которую был отснят клип), "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).
В 1997 году "Кар-Мэн" участвовала в проекте "Сюрприз от Пугачевой", записав ремикс на песню "Робинзон". В этом же году вышел сольный проект Сергея Лемоха "Поларис".
После небольшого затишья в 1998 году вышел альбом "Король диско", вся музыка в котором полностью в стиле (классического) "диско". По причине болезни Алексея Лачинова был задержан выпуск клипа на песню "Тацуйте диско" из альбома "Король диска", который появился только где-то в начале 1999 года.
Через полтора года, в декабре 1999 года, вышел альбом ремиксов на старые хиты (с 1991 по 1994 год).
