As I mentioned in another thread, I had this problem very recently,and man did I get all sorts of advice,the dumbest one being to rub their noses in it!
For sure the first thing to do is get a vets advice, and if you want to avoid the costly visit, you can take in just the urine sample and have it analyzed (that's what I did first). You need to put something (maybe a boot mat) at the spot where he is urinating/deficating that will contain some of the puddle so that you can dump it into a clean container (ew...trust me I know), take a fecal sample as well if possible.
If there is no problem with the urine/feces and kitty is healthy, then it is a behavioural problem which can be solved by adding another litter box, the vet suggests placing it where he is having his "accidents" , then once he is back on track with the litter box, move it to a more private location. Just be sure to take him to the new location and gently
rub his paws in it, as he would when burying his "deposits". Hope this is helpful.
P.S. My cats have never responded well to the word "no"!!!