Ранней осенью 1830 г. любознательный учёный (в нем угадывается сам Мериме) нанимает в Кордове проводника и едет на поиски древней Мунды, где произошло последнее победоносное испанское сражение Юлия Цезаря. Полуденный зной заставляет его искать прибежища в тенистом ущелье. Но место у ручья уже занято. Навстречу рассказчику настороженно поднимается ловкий и сильный малый с мрачным гордым взглядом и светлыми волосами. Путешественник обезоруживает его предложением разделить с ним сигару и трапезу, и дальше они продолжают путь вместе, несмотря на красноречивые знаки проводника. Они останавливаются на ночлег в отдалённой венте. Спутник кладёт рядом мушкетон и засыпает сном праведника, а учёному не спится. Он выходит из дома и видит крадущегося проводника, который собирается предупредить уланский пост, что в венте остановился разбойник Хосе Наварро, за поимку которого обещаны двести дукатов. Путешественник предупреждает спутника об опасности. Теперь они связаны узами дружбы.

Учёный продолжает свои розыски в библиотеке доминиканского монастыря в Кордове. После заката солнца он обычно гуляет по берегу Гвадалкивира. Однажды вечером на набережной к нему подходит женщина, одетая как гризетка, и с пучком жасмина в волосах. Она невысока, молода, хорошо сложена, и у неё огромные раскосые глаза. Учёного поражает её странная, дикая красота и особенно взгляд, одновременно чувственный и дикий. Он угощает её сигаретами, узнает, что её зовут Кармен, что она цыганка и умеет гадать. Он просит разрешения проводить её домой и показать ему своё искусство. Но гадание прервано в самом начале — распахивается дверь, и в комнату с ругательствами врывается закутанный в плащ мужчина. Учёный узнает в нем своего друга Хосе. После яростной перепалки с Кармен на незнакомом языке Хосе выводит гостя из дома и указывает дорогу к гостинице. Учёный обнаруживает, что у него тем временем исчезли золотые часы с боем, которые так понравились Кармен. Огорчённый и пристыженный учёный покидает город. Через несколько месяцев он снова оказывается в Кордове и узнает, что разбойник Хосе Наварро арестован и ждёт казни в тюрьме. Любопытство исследователя местных нравов побуждает учёного посетить разбойника и выслушать его исповедь.

Хосе Лисаррабенгоа рассказывает ему, что он баск, родился в Элисондо и принадлежит к старинному дворянскому роду. После кровавой драки бежит из родного края, вступает в драгунский полк, служит усердно и становится бригадиром. Но однажды, на его несчастье, его назначают в караул на севильскую табачную фабрику. В ту пятницу он впервые видит Кармен — свою любовь, муку и погибель. Вместе с другими девушками она идёт на работу. Во рту у неё цветок акации, и идёт она, поводя бёдрами, как молодая кордовская кобылица. Через два часа вызывают наряд, чтобы прекратить кровавую ссору на фабрике. Хосе должен отвести в тюрьму зачинщицу ссоры Кармен, которая изуродовала ножом лицо одной из работниц. По дороге она рассказывает Хосе трогательную историю о том, что она тоже из страны басков, в Севилье совсем одна, её травят как чужую, потому она и взялась за нож. Она лжёт, как лгала всю жизнь, но Хосе верит ей и помогает бежать. За это он разжалован и на месяц отправлен в тюрьму. Там он получает подарок Кармен — хлебец с напильником, золотой монетой и двумя пиастрами. Но Хосе не хочет бежать — воинская честь удерживает его. Теперь он служит простым солдатом. Однажды он стоит на часах у дома своего полковника. Подъезжает экипаж с цыганами, приглашёнными для увеселения гостей. Среди них Кармен. Она назначает Хосе встречу, они проводят вместе безоглядно счастливый день и ночь. При прощании Кармен говорит: «Мы квиты. Прощай... Знаешь, сынок, мне кажется, я немножко тебя полюбила. Но  волку с собакой не ужиться», Тщетно пытается Хосе найти Кармен. Она появляется только тогда, когда нужно провести контрабандистов через пролом в городской стене, который охраняет Хосе. Так, за обещание Кармен подарить ему ночь он нарушает воинскую присягу. Затем он убивает лейтенанта, которого приводит к себе Кармен. Он становится контрабандистом. Какое-то время он почти счастлив, так как Кармен иногда ласкова с ним — до того дня, когда в отряде контрабандистов появляется Гарсиа Кривой, отвратительный урод. Это муж Кармен, которого ей наконец удаётся вызволить из тюрьмы. Хосе и его «соратники» занимаются контрабандой, грабят и иногда убивают путешественников. Кармен служит им связной и наводчицей. Редкие встречи приносят короткое счастье и нестерпимую боль. Однажды Кармен намекает Хосе, что во время очередного «дела» можно было бы подставить кривого мужа под вражеские пули. Хосе предпочитает убить соперника в честном поединке и становится ромом (по-цыгански мужем) Кармен, но она все более тяготится его навязчивой любовью. Он предлагает ей изменить жизнь, уехать в Новый Свет. Она же поднимает его на смех: «Мы не созданы для того, чтобы сажать капусту». Через некоторое время Хосе узнает, что Кармен увлечена матадором Лукасом. Хосе неистово ревнует и снова предлагает Кармен уехать в Америку. Она отвечает, что ей и в Испании хорошо, а жить с ним она все равно не будет. Хосе везёт Кармен в уединённое ущелье и снова и снова спрашивает, последует ли она за ним. «Любить тебя — не могу. Жить с тобой — не хочу», — отвечает Кармен и срывает с пальца подаренное им кольцо. В ярости Хосе дважды вонзает в неё нож. Он хоронит её в лесу — она всегда хотела обрести вечный покой в лесу — и кладёт в могилу кольцо и маленький крестик.

В четвёртой и последней главе новеллы рассказчик самозабвенно делится с читателями своими наблюдениями над обычаями и языком испанских цыган. Под конец он приводит многозначительную цыганскую пословицу: «В наглухо закрытый рот мухе заказан ход».