The cemetery was named "Valhalla" for the hall of slain warriors presided over by Odin, the Norse god of war and death, amongst other associations.

The Spanish Mission Revival entrance structure was designed by architect Kenneth McDonald Jr. For the decorative stone castings, McDonald hired Italian-born sculptor Federico A. Giorgi, who had created 30-foot-tall (9.1 m) statues of elephants and lions for the 1916 epic film Intolerance, and helped to craft the exterior of downtown's Million Dollar Theater.

Picnickers spread blankets on the surrounding grassy expanse between three reflecting pools and flat cemetery markers, which were a new concept at the time.

On December 17, 1953—the 50th anniversary of Orville and Wilbur Wright's 12-second powered hop at Kitty Hawk—the rotunda was rededicated as the Portal of the Folded Wings, through the efforts of aviation fan and cemetery employee James Gillette.

[3] During the ceremony, the cremated remains of Walter R. Brookins, the first aviator to take a plane to an altitude of a mile and the Wright brothers' first civilian student, were interred.

[2] In 1991, the cemeteries and mortuaries were acquired by Service Corp. International of Houston, but the Pierce Brothers sign remains at Valhalla.