- "Travel back to a time when sawing a women in half was still considered entertainment at this popular Russian Cabaret club."
- ―GTA IV Manual Description
The comedy acts there are much poorer in humor than those of Split Sides Comedy Club, though there are some interesting acts. Like the Split Sides, Niko Bellic can watch shows in the club on his own, on a date, or as an activity with a friend.
The club's interior includes various rooms that serve several purposes in-game. The main feature of the club is its dining area, bar and open space (presumably used as a dance floor) fronted by a stage, where the club's acts are performed. The backstage of the club is accessible from a door to the left of the stage, connecting to the performer's dressing room, a QUB3D video arcade game, and a backlot of the club which leads up to the club's roof, where a hidden gun can be found. A cloakroom is also included between the main entrance and the main room of the club.
Perestroika's shows are triggered from within the club itself; the player must first enter the club and locate the marked checkpoint to the right, where the player is intended to be seated.
The club's exterior design is largely based on the Millenium Atlantic Oceana in Brooklyn.
"Perestroika" ("Перестройка") means "restructuring" when translated from Russian. The term is commonly used to refer to the economic reforms implemented by Soviet Union leader Mikhail Gorbachev during the 1980s which ultimately led to the breakup of the Soviet Union. The naming of the club could be derived from this reform since the clubs owner, Mikhail Faustin, is killed by Niko after being ordered to by Dimitri, who was subordinate to Faustin.
At night, the club is guarded by a bunch of Russian mafia members who will attack if provoked, in and outside the club, if you pull out a gun after you have made the gang members attack you, they will pull out their guns and start shooting at you. The club is also guarded by two gangsters who search guests before they enter (except the player). Depending on how far in the game the player has got, the guards will react in one of two ways. If the player hasn't completed The Master and the Molotov mission, the guards will welcome them. However after this mission is completed, the guards will warn you to stay away and then attack the player.
If, however, accompanied by a friend (whilst the player is doing an activity for his friend), the guard will let them in, despite the mission completion of The Master And The Molotov. If you take Roman there after the mission Crime & Punishment, he may occasionally feel uncomfortable and says it must be where Faustin hangs out when he isn't holding hostages in his basement and shooting them. After completing The Master and the Molotov, he tells Niko it's a shame Faustin is dead because the place is going to pot.
Perestroika hosts a total of four different acts, of which two will be feature each time a player comes to watch its show. The sequence of acts are repeated after six visits. While the club still accessible in The Lost and Damned and The Ballad of Gay Tony, the player is unable to watch any act.
- Perestroika is the venue of the "Porn Idol" auditions that Guy wanted to attend.
- The dialogue and ped model of the woman at the coat check counter are recycled from Alex Chilton's, however they use different textures and models for the hair and clothes.
- In Grand Theft Auto IV "Move Up, Ladies" trailer, Niko is seen entering Perestroika the opening cutscene of Final Destination wearing a suit from Perseus, despite the shop not being available until much later in the game. Either Perseus was available in the beta version of the game earlier on, Faustin's missions were placed later in the game, or most likely the suit was just added while programming the game to make it look classier.
- After The Master and the Molotov, while on a friend activity with Roman, he will say something like it's a big shame your Russian Friend Mr. Faustin is dead.
- In both TLaD and TBoGT, the guard will still attack Johnny Klebitz/Luis Fernando Lopez for unclear reasons, despite that neither protagonists have ever confronted or encountered the Faustin Mafiya before.