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