The city was laid out on the north bank of the lower Des Moines River in 1843 by the Appanoose Rapids and Milling Company. In the following year Ottumwa became the seat of Wapello County. Up through the 1870s the community was essentially confined to the low, hilly area north of the river. The city expanded to the flatlands across the river to the south with the arrival of the meat-packing industry at the end of the 1870s. The largest of these facilities eventually became the extensive John Morrell and Company plant (founded in 1878).

The existence of vast deposits of bituminous coal led to the development of a coal industry. The glowing and optimistic view of what this industry might do for the region's economy was beautifully summed up in the 1890 Coal Palace. 10This fairyland exposition building was one of a series erected in Iowa in the late 1880s and early 1890s—others being the Corn Palace at Sioux City, the Bluegrass Palace at Creston, and the Flax Palace at Forest City. Other, more modest structures were built at Mason City and Algona. Still others, such as an Onion Palace at Davenport, were projected, but not built.

With the success of the earlier Corn Palace at Sioux City before them, the citizens of Ottumwa decided to advertise their own major industry, coal. They engaged the Sioux City architect Charles P. Brown, who was then planning the second corn palace, to design their extravaganza. Brown produced quite a different building from that at Sioux City. The new one was described as being “erected in an architectural style that is a compromise between the Gothic and the Byzantine.” 11In size the structure measured 230 by 130 feet, and its central tower was 200 feet high. The walls of the building were sheathed in uncut blocks of coal, and the crenellated walls projected skyward with spired roofs and bulbous domes with lanterns. Beneath the building, in wonderful Disneyland fashion, was a replica of a coal mine—viewed by visitors within a car which descended and ran through the mine. The palace was used for a second season in 1891, and it was later torn down.