Ursprünglich wurden die Barons als Cleveland Indians im Jahr 1929 gegründet und hießen zwischen 1934 und 1937 Cleveland Falcons und wurden aber 1937 in Barons umbenannt. Ihre erfolgreichsten Jahre hatten sie zwischen 1939 und 1957, in denen sie neunmal den Calder Cup holten (1939, 1941, 1945, 1948, 1951, 1953, 1954, 1957 und 1964) und vier weitere Male das Finale erreichten, in denen sie aber unterlagen (1944, 1946, 1950 und 1956). In den anschließenden 15 Jahren erreichten sie nur noch zweimal das Finale, welches sie 1964 gewannen und zwei Jahre später verloren.
Der herausragende Star der Franchise war Fred Glover, der die Team-Rekorde in den Kategorien Spiele, Tore, Vorlagen, Strafminuten und gespielte Saisons anführt und dort ligaweit an zweiter Stelle steht. Außerdem spielte der Hall of FamerJohnny Bower, der vor seiner NHL-Karriere neun Jahre bei den Barons aktiv war und bis heute der Torhüter mit den meisten Shutouts in der AHL ist. Der damalige General Manager der Barons Jim Hendy ermutigte Bower zu einem Wechsel in die NHL. Weitere berühmte Spieler der Barons-Geschichte waren Les Cunningham, der fünfmal als Liga-All-Star ausgezeichnet wurde und nach dem die Trophäe für den AHL-MVP benannt ist, Jack Gordon, Bill Needham, der Spieler mit den meisten Spielen für die Mannschaft in deren Historie, Cal Sterns, Fred Thurier und Les Binkley.
Als 1972 in Cleveland ein WHA-Team (Cleveland Crusaders) installiert wurde, schwand das Publikumsinteresse und der damalige Besitzer des Teams, Nick Mileti, entschied, die Barons noch während der laufenden Saison im Februar 1973 nach Jacksonville, Florida umziehen zu lassen, wo es bis 1974 spielte und zweimal die Playoffs verpasste. Anschließend wurde das Franchise aufgelöst.