The Smeezingtons went to New York to work with Jeff Bhasker, Emile Haynie and Mark Ronson and during a jamming session with drums, bass, and guitar, Mars created the riff of the song.

He elaborated; "We were just having a jam session, tracking some things, and Bruno started playing this groove and making up something on the spot; we all thought it was pretty good.

"[8] Lawrence believes the lack of "heavy hitting drums" and the presence of a small guitar solo allows the song to be carried by Mars.

Aaron Bay-Schuck, Mars's A&R representative at the time, found the track's production to be cutting edge, although it wasn't an instant favorite.

Bay-Schuck felt the song needed time to grow as "the more you hear it, the more of an earworm it becomes", leading the promotional department to make sure that program directors weren't afraid of playing a track that "sounded different from what was on the radio".

[14] In early November 2013, a CD Single was released on Poland, Germany, Austria and Switzerland, it included the album version of "Locked Out of Heaven", as well as a poster and stickers of Bruno Mars.

[3] It finds Mars singing a confession of a relationship that is so good that he repeats to his love "Your sex takes me to paradise", a verse inspired by Halle Berry;[22][23] "You make me feel like I've been locked out of heaven for too long/ Can I just stay here, spend the rest of my days here?"

"[29] For Paul MacInnes of The Guardian called it "a brazen – but successful – welding of Dire Straits' 'Sultans of Swing' (1978) and 'Can't Stand Losing You' (1978) by the Police.

"[30] Carl Williott of Idolator found out that "the angular guitars and Mars' Sting-like staccato delivery are heavily indebted to The Police," also seeing "hints of Foster the People on the omnipresent 'eh-eh-eh-eh-ooo' punctuating the beat.

"[32] Mikael Wood of the Los Angeles Times likened it to The Police era Ghost in the Machine (1981) heavily influenced by Human League.

"[34] Though critics have pointed out the song's similarities to some of the hits by the Police, Mars told MTV News that he did not intend to write anything mimicking by the Sting-fronted band.

"I don't think it initially tried to sound like anybody else, but I picked up the guitar and just started playing [the song's opening chords]," Mars explained.

[25] John Marx, a partner in the music division at William Morris Endeavor (WME), who was responsible for managing The Moonshine Jungle Tour said "it's the type of song that really motivates people to purchase a ticket.

Robert Copsey of Digital Spy was positive, giving the song a rating of 5 out of 5 stars, praising the "80s-styled funk beats and wildly infectious percussion", the "singalong chorus may be a hasty reminder that his strength lies in fist-clenching".

[31] Ryan Reed of Paste Magazine called it "a driving pop anthem that moves from a punchy, 'Roxanne'-esque new-wave groove to a soulful, synth-driven chorus.

"[37] Matt Cibula of PopMatters further explained, writing, "It starts out like an early Police single, with some straight-up Reggatta de Blanc syncopation and a shockingly good Sting vocal impression.

"[38] Kitty Empire of The Observer wrote that the song "channels the Police, but its 21st-century builds owe as much to rave-pop as they do to producer Mark Ronson.

"[39] Jason Lipshut of Billboard gave a very positive review, stating that the song is "Mars's best solo single to date, with the singer-songwriter yelping about fornication as a tossed salad of chopped guitars and vocal exclamations buttress his sumptuous leading-man act.

"[40] Melinda Newman of HitFix praised "Mars' singing and the catchy little background vocals," which according to her, "keep the song moving downstream at a rapid pace."

She also noted that "Even clumsy lyrics like 'your sex takes me to paradise' can't diminish that joy that the beats and melody bring.

[74] The single has received a six-times platinum certification from the Recording Industry Association of New Zealand (RMNZ), denoting sales of 180,000 copies.

The music video was filmed using "an old VHS camera", with Mars and The Hooligans performing, and playing along with the single live multiple times.

[79] The concept of the video shows Mars having a good time with his bandmates, doing things like smoking, drinking beer and playing games.

"[81] Rolling Stone, commented that the video takes place "in a dingy club", however, "the real attraction here are the grainy visuals filmed in fake fuzziness, giving the clip a retro feel.

"[82] Chris Martins of Spin magazine said the video's vintage style "may be slightly off since the [song] sounds far more Sting than Curtis Mayfield", but regarded it as "a good one nonetheless.

"[86] Sam Lansky of Idolator praised the performance, writing that "Mars turned it out on the show, with an energetic rendition of 'Locked Out of Heaven' backed by a fleet of impeccably choreographed dancers.

[93][94][95] On February 2, 2014, the single was featured as the third number in the mini-set medley, in the halftime performance of Super Bowl XLVIII at MetLife Stadium in New Jersey.

[98][99] British quartet Bastille covered "Locked Out of Heaven" for BBC Radio 1 DJ Sara Cox in the Live Lounge on January 21, 2013.

The band's version saw a mash-up between the track and Rihanna's "Diamonds"; also incorporating "Niggas in Paris" by Jay-Z and Kanye West and "Angels" by The xx.

[104] English singer Amelia Lily performed the song in her set on the Girls Aloud Ten: The Hits Tour in 2013 and during her summer gigs.