La, La, La, He, He, Hee was released as the b-side of Sign O' The Times, the first single from Prince's ninth album Sign O' The Times. The 12" version of the single contained the original full-length version, over three times the length of the version included on the 7" single.
In 1993, it was included as the 13th track on The B-Sides compilation (included as the third and final disc on The Hits / The B-Sides).
While specific recording dates are not known, basic tracking of the track, originally titled My Tree, took place in mid-January 1987 at Prince's Galpin Blvd Home Studio in Chanhassen, Minnesota after completion of the Sign O' The Times album (during the same set of sessions that produced Come Home and overdubs onto 77 Bleeker St.).
According to the liner notes of The B-Sides, the track was created as a response to a dare by Sheena Easton who claimed that Prince couldn't write a song from such a basic phrase (resulting in her writing co-credit).
In a 2012 interview, however, Sheena Easton indicates that her writing role was slightly larger:
"That was something I was writing, just a stupid little thing. See, I have six cats. It was about a cat up in a tree teasing a dog. I was actually being sarcastic. He said, 'Ya, that could be a song,' and I was like 'Oh ya, like what do you want me to sing? La La La, He He He – I love you, you love me? That's how talented I am?' He said, 'Actually, that'd be kind of cute! Go ahead and write it.' I don't really write any more as I'm out of the game now, but back then, that was my thing. Then, all my songs were little stories. I liked storytelling songs. He used to think they were amusing. I don't think other people did but he used to think they were."