Inspirert av det britiske kjendismagasinet «OK!», «OK! Puzzle Stars' setter spilleren som rollen som en sjefredaktør, som må løse en rekke gåter for å sende 12 OK! magasiner til butikkene. Spillet bruker hovedsakelig Nintendo DS-pennen for spilling og inkluderer oppgaver som Wordsearches, Crosswords, Sudoku, Fitword og så videre. Spilleren må holde Nintendo DS-konsollen sidelengs for å spille spillet. Start-knappen brukes også til å sette et puslespill på pause når som helst og henter frem pausemenyen (som inkluderer alternativer for å fortsette puslespillet, lære håndskriftgjenkjenning for å passe spillerens håndskriftmodus, eller for å avslutte puslespillet). Hvert problem i spillet inkluderer 16 oppgaver å løse, og for hver 4 løste må spilleren løse et spesielt puslespill kalt en 'Puzzle Star' (som belønner spilleren et coverelement for gjeldende utgave). Når alle 4 omslagselementene er oppnådd for ett nummer, går spilleren videre til det neste til alle 12 er fullført. For hvert puslespill som er fullført, tildeles spilleren en OK! Skrapekort. Her må spillere bruke Nintendo DS-pennen for å gni én av 3 stjerner som vises for å vinne et visst antall stjerner (som lar spillere kjøpe hint i en vanskelig situasjon). Spillet inkluderer en rekke kjente kjendisbilder gjennom Bonus Puzzles (så vel som utgaveomslagene) og viser fascinerende kjendisfakta under lagringsprosessene.