Robert Taira founded the company, then called Robert's Bakery, in Hilo, Hawaii, in the late 1950s.
In the early 1960s, the company moved to Honolulu and changed its name to King's Hawaiian.
By the 1980s, Taira's company, King's Hawaiian Bakery, was grossing US$20 million annually. In 1988, the company established their current corporate headquarters in Torrance, California.
Fast food restaurant chain Arby's seasonally sells sandwiches featuring King's Hawaiian buns. The sandwiches are Kings Hawaiian BLT and Roast Beef and Swiss (which includes Grey Poupon Honey Dijon mustard). There is also a seasonally-available King's Hawaiian Fish (which includes a slice of tomato and a slice of Market Cheddar, along with the usual lettuce and tartar sauce). September 2014, a Barbecue Brisket sandwich on the Kings Hawaiian buns was introduced. It is named "BBQ Brisket Sandwich" 
In 2016, King's launched a new line of BBQ Sauces consisting of four flavors; Big Island Lava, Smoked Bacon, Original Sweet Pineapple, and Kona Coffee.
In 2016, King's Hawaiian entered a three story tall float representing the beauty of the Hawaiian Islands in the Macy's Thanksgiving Day Parade. The float included a volcano that erupted confetti and a stage for musical performers.