I always wondered, doesn't that require the clocks to be synchronized?

Like, what happens if I set my phone to a different time?

What if the server has lost connectivity to an NTP service and its clock is a few minutes off?

In practice, it's not the exact timestamp, down to the millisecond--there's a window of 30 seconds or so for each code. On top of that, some services will also accept one of the last (or next) few valid codes too. So it needs to be roughly synchronized, but not impractically so.

Some systems have some extra magic that allow the server to adjust for each device's clock skew; this was particularly important for hardware tokens that didn't have network connections. To imagine how that might work, suppose the server normally accepts responses that are valid at times t-2, t-1, t (the current time, per the server), t+1, and t+2. If a user consistently replies with the t-1 token, we know that her device is running slightly behind and we can instead authenticate against t-3, t-2, t-1, t, t+1.

In addition to this, it's worth mentioning that the two sides can go out of sync, and if so, there are ways to fix that.

The TOTP implementation for AWS logins is particularly prone to doing this for some reason, and you have to enter simultaneous TOTP codes to resync.