Samba Em Preludio is in B minor, as indicated by the key signature.

Bossa novas tend to be in a minor key, which helps bring out the mellow and nostalgic nature of the style.

Perfect cadences are used which reinforce the tonal centre of B. An example is the start of the second verse at bar 23 (1'19). A clear tonic chord of Bm is heard on the downbeat preceded by Spalding's bass note of an F sharp (V-I). This makes the key secure and definite.

Though the multiple accidentals and chromatic notes of the song may make it seem as though there are modulations, this is not the case. As is the case in jazz harmony, chromatic passing notes and other substitutions are often used to bring out contrasting harmonic colour. Chord changes often travel through other keys but these are usually very brief and can't be described as actual key changes.