1928年7月18日、ルイジアナ州モンローに生まれる。サックスとヴァイオリンの演奏家であった父親からジャズを学び、高校在学中には父親のバンドに出演することもあった。その後、ルイジアナ大学モンロー校に入学し、同校に2年通ったのちルイジアナ州立大学に転入し、音楽教育学の学士号を取得し卒業した。
卒業の翌年（1951年）、ウディ・ハーマンのバンドにレギュラー・メンバーであるアービー・グリーンの代役として出演し、本格的なプロ活動を開始する。このとき、ウディ・ハーマンから即興演奏の技術を高く評価され、アービー・グリーンがバンドに復帰した後もレギュラー・メンバーとして残ることができた。
ウディ・ハーマンのバンドに3年所属したのち、フォンタナは1954年にライオネル・ハンプトンのバンドに加わり、その後はスタン・ケントンのバンドにも参加している。スタン・ケントンのバンドではアルバム3枚に参加し、同バンドに所属していたカイ・ウィンディングと共演を果たしている。
これらのバンドとともに数多くのツアーやレコーディングをこなすにつれ、フォンタナは抒情的で独創的なソリストとして知られるようになる。彼の流れるようなプレイスタイルは、J・J・ジョンソンやフランク・ロソリーノなど、これまでのジャズ・トロンボーン奏者のスタイルとは大きく異なるものであった。特に、彼の代名詞とも言える「ドゥードル・タンギング」という奏法は、多くのジャズ・トロンボニストに絶賛された。この奏法は、それまでスライド・トロンボーンでは演奏不可能と思われた速いテンポにおいても滑らかに演奏することを可能にした。
