ローマ時代のフュッセンは、「Via Claudia Augusta」というローマ街道の経路上にある入植地であった。このローマ街道を南へ進むとイタリア北部に通じ、北へ進むとローマ帝国のラエティア属州の中心都市へと通じていた。その中心都市はアウグスタ・ヴィンテリコールムと言い、これは現在のアウクスブルクに当たる。古代末期には、アルプスを越える重要な交易路を警備するため、ローマ軍団の一つである第3軍団イタリカの部隊がフュッセンに駐屯した。フュッセンを発掘した結果、5世紀のローマ人の城郭基礎が出土した。おそらく260年にはすでにここにローマの軍事施設があったと推測されている。フュッセンの、当時の「Foetibus」または「Foetes」という名前は、ラテン語で「渓谷」を意味する「Fauces」またはゲルマン語で「麓、足」を意味する fot に由来する。その後集落名は Fozen（1147年）、Fozin（1188年）、Fuozzen（1206年）、Füzzen（1366年）と変遷した後、現在の Füssen（1424年以降）となった。

 現在の聖マング修道院教会

フュッセンがその守護聖人として崇める聖マング（フュッセンのマグヌス）は、748年にこの集落に庵を設けた。その後修道士が流入し、8世紀にはベネディクト会の聖マング修道院が創設された。聖マングの最初の埋葬地は、彼が建てた小さな教会であった。その後、彼の遺骨は850年に建てられた教会の地下室に移されたが、1100年頃にその遺骨は紛失した。今日では、聖マング修道院教会の地下室の埋葬地を見る事が出来る。聖マングの唯一の遺骨は聖遺物とされ、大祭壇の上のガラスの十字架の中に納められている。同じ十字架の中には彼の杖、胸の十字架、聖杯も納められている。

同じ8世紀頃に、フランク王国の王領が設けられた。代官権は初めヴェルフェン家に属したが、1191年にヴェルフェン家の世襲財産としてシュタウフェン家が購入した。1268年にコッラディーノがナポリで処刑された後、シュヴァーベン公領は帝国に返還された。

その間にレヒ川沿いの入植地は発展を遂げた。13世紀には当時のアルゴイ地方では最大の規模の都市となっていた。都市権の授与がいつであったかは定かではないが、フュッセンを「都市」と表記している1295年の史料が遺されている。

1313年に皇帝ハインリヒ7世は、400マルク銀貨の借金のために、この街と周辺地域をアウクスブルク司教に質入れした。この借金は返済されなかった。皇帝の後継者達は1314年（フリードリヒ美王）、1322年（ルートヴィヒ・フォン・バイエルン）によって、その所有を認められた。カール4世によってアウクスブルク司教に裁判権が移譲されたことで、フュッセン帝国代官管理区は最終的に司教領となった。

 1656年のフュッセン図

1486年から1505年にかけてアウクスブルク司教領主は中世都市の上にホーエ・シュロス（高い城館）を建造した。当時の後期ゴシック様式の城館は、その後は聖界領主の夏の離宮として用いられた。アルゴイ地方では大きな城で、ゴシック建築の城郭建築として大変良く保存されている。フュッセンのランドマークとなっているこの城館は、バイエルン州の絵画コレクションの展示支所となっており、ゴシック様式後期およびルネサンス期の美術品を中心に展示している。カトリックの都市であったフュッセンは、シュマルカルデン戦争の際にはプロテスタントの傭兵隊長ゼバスティアン・シェルトリン率いる高地ドイツ都市軍によって、1546年7月10日に占領された。現在の修道院教会は1701年から1726年に建設された。

1745年4月22日にこの街は、一時的に国際的重要性を獲得した。フュッセン条約でバイエルン選帝侯マクシミリアン3世ヨーゼフはオーストリアに対する相続請求権を放棄し、バイエルンにおける政治権力確立に専念することとなった。バイエルンは、父親の皇帝カール・アルブレヒトが引き起こしたオーストリア継承戦争から離脱した。1782年5月6日、ウィーンからローマへ戻る途中アウクスブルクから到着した教皇ピウス6世はホーエ・シュロスに宿泊した。

1803年の帝国代表者会議主要決議に基づく世俗化の結果、バイエルン選帝侯領の一部となった。例外は、一つはフランチェスコ会修道院で、1803年にドイツ騎士団領となり、1805年になってバイエルン選帝侯領に移された。もう一つは聖マング修道院で、エッティンゲン＝ヴァラーシュタイン侯の城館となり、1806年になって初めてバイエルン領となったのである。

フュッセンは、この地を拠点にしたリュート製作者やヴァイオリン製作者といった特殊な手工業者によって有名となった。フュッセンはヨーロッパにおける職業的ヴァイオリン製作の揺籃の地となったのである。1562年にはヨーロッパで初のヴァイオリン製作者のツンフトが設立された。

第二次世界大戦中は、ダッハウ強制収容所の支所がフュッセンに置かれた。

市域の拡大

バート・ファウレンバッハは1921年にフュッセン市に合併した。1978年の市町村再編に伴いホプフェン・アム・ゼーおよびヴァイセンゼーがこの街に合併した。