By the time of its recording, the pianist and bandleader Thelonious Monk had overcome an extended period of career difficulties and achieved stardom with his residency at New York's Five Spot Café, beginning in 1957.

Misterioso's title was meant to evoke Monk's reputation as an enigmatic, challenging performer, while its cover art was part of Riverside's attempt to capitalize on his popularity with intellectual and bohemian audiences; it appropriated Giorgio de Chirico's 1915 painting The Seer.

Monk's manager, Harry Colomby, led an appeal on the pianist's behalf in front of the State Liquor Authority (SLA) to have his card restored.

Colomby argued to the SLA that Monk was "a drug-free, law-abiding citizen, whose productivity and growing popularity as a recording artist demonstrates his standing as a responsible working musician".

"[3] Joe Termini, who co-owned the venue with his brother Iggy, testified at Monk's police hearing, which resulted in the reinstatement of his cabaret card and his employment at the Five Spot Café.

[3] In his first stable job in years, Monk helped transform the small bar into one of the city's most popular venues, as it attracted bohemians, hipsters, and devout fans of the pianist's music.

[5] However, by the time it ended in December, he had lost Wilson to poor health, while Coltrane left in pursuit of a solo career and a return to Miles Davis's group.

[6] Monk returned to New York's club scene in 1958 with a new quartet and received an eight-week offer from Joe and Iggy Termini to play the venue again, beginning on June 12.

[17] Griffin's solo vamp maintained the rhythm while quoting lines from other pieces, including the theme song for the animated Popeye theatrical shorts; he played "The Sailor's Hornpipe" at the end of "Blues Five Spot".

[17] According to Keepnews, the album and its title track were named as a slight play on the words "mist" and "mystery", meant to evoke the perception of Monk's music as enigmatic and challenging at the time.

"[24] To capitalize on Monk's popularity with intellectual and bohemian fans from venues such as the Five Spot Café, Riverside released Misterioso and reissues of his older records with designs that appropriated 20th century works of art.

'"[25] In the opinion of musicologist Robert G. O'Meally, the cover reflected "the mysterious violations of convention of perspective, the silences, and oddly attractive angles (the overall futuristic quality) in Monk's music".

[28] The following March, Monk was voted pianist of the year in an annual poll of international jazz critics from Down Beat magazine, who said he was heard "at his challenging, consistently creative best" on Misterioso.

He found its music on-par with Monk's usual standards and highlighted by exceptional playing by him and the rhythm section, particularly Haynes, who showed "once again what a great drummer he was then—and, indeed, still is today".

However, Fox felt that Griffin did not fit in with the quartet and overshadowed Monk's compositions, finding the saxophonist's solos diffuse and characterized by trivial quotations rather than musical development.

[22] In the All Music Guide to Jazz (2002), Lindsay Planer wrote that Monk's quartet "continually reinvented" their strong, cohesive sound with "overwhelming and instinctual capacities" throughout Misterioso.

[38] Liam McManus from PopMatters was less enthusiastic about Griffin's playing, which he believed was occasionally heavy-handed and detracted from the music, but still recommended Misterioso as an exceptional Monk record featuring the pianist in a casual performance with his quartet.