A vet check for a UTI or other medical issue should always be the first thing when a cat starts inappropriately urinating. If he checks out okay then you start thinking about your litter box management --
Are you scooping as frequently as always?
Have you changed litter?
Have you emptied and thoroughly scrubbed the boxes recently?
Are the boxes old and maybe need replacing?
Do you have enough boxes (general rule is one per cat plus one more)?
Are they conveniently located as far as kitty is concerned?
If litter box management is okay, then consider trying some Feliway and switch to Dr. Elsey's Cat Attract litter.
It often helps to confine kitty to a small room of his own for a couple of weeks for litter box retraining.
There are anti-depressant type medications that can help. Your vet can tell you about those.