Historia 200px|thumb|left|Jim Matheos podczas koncertu 21 listopada 2007 roku Powstała w 1982 roku w Hartford w stanie Connecticut pod nazwą Misfit. W skład zespołu weszli: wokalista John Arch, gitarzyści Jim Matheos i Victor Arduini, basista Joe DiBiase oraz perkusista Steve Zimmerman. W 1983 roku ukazało się pierwsze demo formacji pt. Rehearsal 1983. Rok później muzycy zarejestrowali drugie demo pt. Misfit. Również w 1984 roku zespół przyjął nazwą Fates Warning. Ukazała się także kolejna kaseta demo - Demo 1984.
Dorobek młodego zespołu wzbudził zainteresowanie wytwórni muzycznej Metal Blade Records, która wkrótce podpisała z muzykami kontrakt wydawniczy. 9 września, także 1984 roku ukazał się debiutancki album zespołu zatytułowany Night on Bröcken. Na płytę trafiły wczesne kompozycje zespołu inspirowane dokonaniami Iron Maiden. Drugi album studyjny pt. The Spectre Within ukazał się 15 października 1985 roku. Wkrótce po nagraniach fromację opuścił Arduini, którego podczas koncertów zastąpił Frank Aresti znany z występów w grupie Demonax.