If you’re both in fairly close relation to the deceased person (especially if family), then 御愁傷様でした (or でございます) would be fine. If not, I would second @RysingDragon is recommend お悔やみ申し上げます. It’s mostly conjecture on my part, but I understand 御愁傷様 to indicate a more sympathetic tone to it.
Or you could go the full mile and say この度は誠にご愁傷様でした。心よりお悔やみ申し上げます。I don’t think you can go wrong with the full spiel.