The first FYE store opened in 1993 at the Trumbull Mall (now Westfield Trumbull) in Trumbull, Connecticut. A second one would later open in 1995 at Eastview Mall in Victor, New York, and a third at Colonie Center in Colonie, New York in 1997.
In 2001, Trans World unified its other mall-based stores under the "f.y.e." name after buying out Camelot Music. During that year, a major re-branding campaign made f.y.e. the brand name for all of Trans World Entertainment's mall-based retail stores as well as many freestanding locations, though some freestanding or strip mall stores continued to operate under regional brands like Planet Music. In 2016 the company changed the store and website branding to "FYE".
In 2006, Trans World began remodeling buildings that were former Coconut stores and Media Play outlets near Salt Lake City, Utah and Buffalo, New York into FYE superstores. In 2009 FYE closed over 100 locations and 52 more in 2012.
In 2016 saw Trans World opening new FYE concept stores in multiple locations (such as the Rockaway Townsquare in Rockaway, New Jersey), with a new logo and look, a larger focus on pop-culture related items, an expanded selection of vinyl records and modern turntables, while the selection of Blu-Rays, DVDs and CDs has been reduced.
In March 2017, FYE founder and CEO Bob Higgins died. Higgins was responsible for the creating the FYE brand as well as maintaining its profitability and therefore its status as the last remaining music chain store.
In November 2018, FYE's parent company was accused in federal court of deceiving customers by asking them to sign up for “free” and or “loyalty” membership programs and magazine subscriptions while charging their credit and debit cards $11.99 per month until customers canceled the services. Another allegation was that customer information was shared with marketing company Synapse without customer consent.
In 2018, 33 FYE stores were closed and 35 more are to be closed before the end of Transworld's fiscal year on February 2, 2019.