Definitely change your password, no matter what.
- are you sure the email you received is legitimate? Or could it have been spoofed somehow?
- if you can review logins, then check if what you see is what the email says
- is there an explanation involving your own activity? Did you use a new network, your phone, something else, which you don't normally do?
- could this be a matter of your connection having changed IP (possible if your were on a consummer-grade ISP) - and if so, do you still have that IP?
- could this be a case of your re-using a password, for example between firstname.lastname@example.org and email@example.com)?
If you can enable 2 factor auth, do so.
You might also consider using something like KeePass if you don't already, and go around to change all your passwords to something totally random, and unique per service.