Although it may not look the part now, the Vienna Bakery building was built as a Victorian-style commercial store in 1893 by John S. Armstrong. Armstrong was postmaster in Tempe, president of the Farmers and Merchants Bank, and he introduced the bill that established the Territorial Normal School for Tempe in 1885. The building itself was originally a drugstore for three years before changing into a post office. The post office did not last very long either and was only in the building until 1900. Charles Bauer seized the opportunity and leased the building in 1904. Bauer opened up the Vienna Bakery and the business operated until 1963.

Today, the building does not look like Victorian architecture at all. This is because, in 1928, the building was remodeled into the popular Spanish Colonial Revival architecture, much like other buildings on Mill Avenue, including the Casa Loma Building. Spanish Colonial Revival-style architecture was made popular by the completion of the Panama Canal in 1914. The Panama-California Exposition from 1915-1917 took place in San Diego and showcased the architectural style pioneered by Bertram Goodhue.

"This is the only example of Commercial Victorian-style architecture in downtown Tempe. It served as a drug store as well as the local post office before becoming a bakery. This building is listed on the National Register of Historic Places, and received a Tempe Beautification Award of Merit in 1981." (Tempe Preservation, Mill Ave Tour)