Sesame Workshop sued the team behind the film for the tagline, "No sesame. All street," claiming that the film tarnishes their reputation. The suit was rejected on May 30, 2018. Soon after, STX issued a brief statement, "We fluffing love Sesame Street (1969) and we're obviously very pleased that the ruling reinforced what STX's intention was from the very beginning - to honor the heritage of The Jim Henson Company's previous award-winning creations while drawing a clear distinction between any Muppets or Sesame Street characters and the new world Brian Henson and team created. We believe we accomplished that with the very straightforward NO SESAME, ALL STREET tagline. We look forward to continued happytimes as we prepare to release Happytime Murders this summer." Some TV spots for the film started with "From the studio that was sued by Sesame Street..."
A total of 125 puppets are in the film, with 40 specifically created for it. All of the sets were built so that puppeteers could stand on the floor and operate the puppets as if they were standing with straight arms. The floor of the sets came up in pieces, so the human actors had a two-foot margin to stay on their path.
Brian Henson's worst day on set was when he had to play Crab. He had to be inside a trash can so that he could direct while operating and voice Crab. While he was in there, he suddenly felt something cold and liquid creeping down his back. A crew member who thought it was a real trash can had carelessly thrown in a half-full bottle of beer.
In the scene where detective Phillips talks to his secretary she mentions a disgruntled client wants to "sew your a**hole closed and keep feeding you and feeding you and feeding you." This is a direct quote from the opening of Wu-Tang Clan's "Method Man" where Raekwon and Method Man spew violent and disgusting threats at each other.
Puppets featured in That Puppet Game Show (2013) play characters and extras in the movie. Eddie Watts is a waiter in the restaurant Phil and Larry Shenanigans are talking in, on the wall photo and in the background. Clyde Stravinsky as the crab in the garbage can at the beach. Jake Hamilton-Jones as the little girl's father who Phil accidentally shoots. Dr. Strabismus as the doctor at the puppet clinic who refuses to operate on Connie. One of the singing Hot Dogs appears during the end credits.
The first red band trailer was released on May 18, 2018 with attached screenings to Deadpool 2 (2018). The music that plays in the scene where Connie fights the other muppets after snorting cocaine is the song Nobody Speak by DJ Shadow/Run The Jewels, which was also played in Deadpool 2 where Wade and Weasel were interviewing the X Force members.