Joker a jeho Phantom Thieves během rutinní hlídky v Mementos nalézají filmové plátno, které slouží jako brána do nadpřirozeného kina. Jako jeho nedobrovolní návštěvníci musí odhalit jeho tajemství, související s jeho manažerkou Nagi a jedinou další návštěvnicí Hikari. Cesta je zavede do několika filmů v podobě labyrintů plných nepřátel, jejichž nešťastné konce musí Phantom Thieves svými činy zvrátit. Během návštěv filmových labyrintů se k Phantom Thieves přidají i členové Investigation Team a SEES.

New Cinema Laybirinth je po Shadow of the Labyrinth druhým dílem crossoverové série Persona Q, kombinující hratelnost série Etrian Odyssey a tématiku série Persona. Ačkoliv se příběh tentokrát točí primárně okolo protagonistů Persona 5, vrací se i hrdinové z Persona 3 a 4, ke kterým se nově přidává i hlavní hrdinka z alternativní cesty Persona 3 Portable. Po stránce hratelnosti se hra značně podobá prvnímu dílu a opět se jedná o dungeon RPG, v němž hráčova skupina prochází dungeon labyrinty z pohledu první osoby, bojuje v tahových soubojích s nepřáteli a řeší různé hádanky.