Kolejny singiel „Te quiero” wydany 10 maja 2010, zajął czwarte miejsce na liście walońskiej oraz siedemnaste na liście flamandzkiej w Belgii (osiągnął status złotej płyty). Znalazł się na liście także w Szwajcarii, Holandii i Francji. Siódmy singel artysty, „House’llelujah”, uplasował się na 22. miejscu listy walońskiej w Belgii. Kolejny singel to „Rail de musique”. Dziewiąty singel „Peace or Violence” dotarł do dwunastego miejsca walońskiej listy (Belgia). Był także notowany na liście austriackiej.
W celu wydania jego debiutanckiego albumu studyjnego, Stromae podpisał kontrakt z wytwórnią Mercury Records, a album zatytułowany Cheese został wydany 11 czerwca. Album zajął pierwsze miejsce na liście walońskiej w Belgii, a na liście flamandzkiej siódme (pokrył się potrójną platyną). W Grecji album zajął czwarte miejsce, a we Francji album dotarł do szóstej pozycji, cztery lata po premierze (uzyskał status złota, sprzedano ponad 260 000 egzemplarzy). Był notowany także w Szwajcarii, Niemczech, Austrii, Kanadzie i Holandii.