Фикельмон происходил из небогатой старинной бельгийско-лотарингской семьи. Его дед и отец, Христиан-Максимилиан Фикельмон, были французскими подданными, но служили в австрийской армии. Образование Карл-Людвиг получил в коллеже в Нанси. Эмигрировал из Франции вместе с отцом в 1792 году. В этом же году поступил в Австрии в драгунский полк Латура. В звании полковника с 1809 года. В Испании (1812—1813) воевал в армии генерала Кастаньоса в качестве командира полка. Вернулся из Испании в Австрию в 1813 году. Произведён в генерал-майоры в 1814 году. В 1815 году был командиром конницы корпуса генерала Фримона, с ним дошёл до Лиона. По отзыву герцога Веллингтона, Фикельмон был самым лучшим кавалерийским генералом, которого тот когда-либо знал.
Позже, не выходя в отставку, Фикельмон перешёл на дипломатическую службу. Был военным атташе (по другим сведениям — посланником) в Швеции. В 1819 году — австрийский посланник во Флоренции. Там познакомился с семьёй Хитрово и в 1821 году женился на Доротее (Долли) Тизенгаузен, дочери Е. М. Хитрово.
Состоял при штабе армии Фримона в 1821 году во время подавления неаполитанской революции. С 1821 по 1829 гг. был дипломатическим представителем Австрии в Неаполе. В начале 1829 года был послан Меттернихом в Петербург для выяснения возможности сближения Австрии и России в ущерб союзу последней с Англией и Францией. Поручение Фикельмон выполнил успешно, лично встретившись с императором. Весной 1829 года Николай I через русского посла в Вене Д. П. Татищева передал пожелание видеть Фикельмона послом в Санкт-Петербурге. В 1830 году Фикельмон был произведён в чин фельдмаршала-лейтенанта австрийской армии. В ноябре 1833 года послу был пожалован орден Андрея Первозванного.
В 1839 году был вызван в Вену и временно замещал Меттерниха на посту канцлера, после возвратился в Петербург. В 1840 году оставил свой пост в России. При отъезде получил бриллиантовые знаки к ордену Андрея Первозванного.
В Вене был назначен на пост Staats und Konferenzminister (приблизительно соответствовал должности министра без портфеля), до 1848 года выполнял различные дипломатические поручения. По мнению его жены, Дарьи Фёдоровны, Фикельмон в этот период был фактически отстранён Меттернихом от серьёзной политической деятельности. Во время революции 1848 года Фикельмон вошёл в состав первого конституционного кабинета. После отставки графа Коловрата ненадолго стал председателем совета министров. Вскоре был пущен слух о том, что Фикельмон «продался России». 22 апреля 1848 года его жена писала Екатерине Тизенгаузен:
В отставку вышел 3 мая 1848 года после демонстрации студентов, направленной против министра-русофила, политического деятеля школы Меттерниха, каким считался Фикельмон. Его дом накануне на несколько часов был осаждён демонстрантами, власти и национальная гвардия устранились от решения конфликта, а войска Фикельмон не вызывал, чтобы избежать кровопролития. Политикой Фикельмон более не занимался. Жил в Вене, а с 1855 года — в Венеции, где вместе с зятем, князем Кляри-и-Альдринген владел дворцом (palazzo Clary). Последние годы жизни отдал литературной деятельности. П. И. Бартенев писал о Фикельмоне:
Фикельмон всегда оставался последовательным русофилом. Об авторе книги «Россия в 1839 году» маркизе де Кюстине он писал:
К Николаю I сохранил на всю жизнь благоговейное отношение, считая его воплощением непреклонной воли. Несмотря на это, в своих произведениях Фикельмон резко критиковал позицию императора в восточном вопросе, что, однако, не помешало ему поддерживать Россию в время Крымской войны.
Zum k?nftigen frieden. Wien (1856)