The Cottonwood Mall theater opened on 10 July 1968 with an invitational premiere of "The Thomas Crown Affair." The theater, which had 850 seats and a "four dimensional sound system," was originally called the "Fox Cottonwood Mall." Construction of the theater was begun by Fox Intermountain Theatres, but by the time it was completed the theater chain had become National General Corporation.

In October 1976, Mann Theatres announced it would convert the Fox Cottonwood Mall Theater into a million-dollar, four-screen theater complex.  The first two theaters, created by splitting the original auditorium, opened in December 1976 and seated about 550 and 330.  Two other two theaters, each seating about 300, were built in an addition on the north side of the building and were to open in January or February of 1977.  The remodeling was done by Horman Construction Co., owners and developers of Cottonwood Mall.  The architect was Mel Glatz and Associates, the same firm that designed the original theater.¹

In 1982 a new triplex was built down the street and was originally called Cottonwood 5-6-7, as if it was an extension of the Cottonwood Mall theater, but it was generally referred to as the Creekside Cinemas.

The Cottonwood Mall 4 had one large theater with about 500 seats and showed several films in 70mm, including "Batman," "2010," and "Brainstorm." Before being split, the theater had two Norelco-AA/2 projectors with Stong Futura-2 carbon arc lamps. One of the Norelco projectors was later moved, possibly to the Creekside theaters.

In 2001, Carmike Cinemas installed new projectors and added digital sound to two auditoriums that didn't already have it. Despite this effort to improve the theater, attendance declined because of the many new multiplexes built in the area. The theater closed on 14 February 2002.

During its last couple days of operation the phone recording at the theater said, "We will be closing our doors for the last time on Valentine's Day, the 14th. So come in and see a movie here for the last time. We would like to thank everyone, and especially thanks for our regulars, for coming in."