Rebecca Leina'ala Kalama Heine (c. 1940 – September 9, 2015) was an American kumu hula and hula instructor. In 1976, Heine established Na Pualei O Likolehua, a nonprofit hālau which trains girls and young women in both hula and Hawaiian cultural traditions.
Heine was raised by her mother, Rebecca Beke Paiaina, a lei maker. She initially attended the Kamehameha Schools, but graduated from President William McKinley High School in 1958. Her first job was at the a Waikiki eatery called Woody's Restaurant. She married her husband, Samuel Ladd Heine, in 1963, with whom she had four children.
She studied hula under several well-known teachers, including Ruby Ahakuelo, Leilani Alama, Puanani Alama, Tom Hiona, Joseph Kahaulelio and Rose Maunakea. Heine was a student of Ma'iki Aiu Lake, an influential kumu hula, graduating from Lake's school in 1973. She was one of a notable group of hula students, also including Robert Cazimero and Wayne Chang, who attended Lake's hālau during the early 1970s.
In addition to establishing the Na Pualei O Likolehua hālau, Heine was a co-founder of Ka 'Aha Hula 'O Halauaola, a major hula conference which was first held in Hilo. Heine was a regular performer at the Prince Lot Hula Festival, held at the Moanalua Gardens in Honolulu. She was also a judge and participant at the Merrie Monarch Festival, a week-long festival held located in Hilo, and a mentor to hula dancers at the Queen Lili'uokalani Keiki Hula Competition.
Heine performed hula solo with The Brothers Cazimero, the Hawaiian musical duo composed of Robert and Roland Cazimero, earning her the nickname, "the third brother." Their professional relationship dates to 1976.
In 2010, Heine chose the theme song for the Prince Lot Festival, "Na Punawai O Moanalua," which translates to "The Wellspring of Moanalua". She explained the chose of the song in an interview with the Honolulu Star-Advertiser, telling the newspaper, "All of life is water. Without water, there is no life."
She made a cameo appearance in a 2013 episode of Hawaii Five-0 called "Ola Na Iwi: Haloa."
Leina'ala Kalama Heine died on September 9, 2015, at the age of 75.