O2 sensor is definitley the 1st place to look. Past that, being that you didn't say if it was a carb or a F/I system. the next place to look is the fuel filter. You'd be surprised at just how much crap can build up in them slowly over time and choke your engine off.
I'd also be looking at the entire spark plug/plug harness/distributor system. It wouldn't be the 1st time that a set of plug's went bad (or worse, were the wrong type installed) and literally choked the engine to death. Same for the plug wires. They have a tendency to go bad from the inside out and looking at them, well, you'd never suspect them, dry rot being the sneaky sucker that we've all grown to know and hate. And don't forget the distributor and rotor. They can both go bad and look completely normal until you pull them off and get a real good look inside them. This a real good reason, expensive as it is up front, to swap out EVERYTHING when you do a tune-up. The easy part is that you can do almost everything yourself, minus the OB computer having to be re-set by a shop that has a system to set your OB engine computer back to factory 'zero'. But the eventual payout is, on the backend, in that once you've done the complete tune-up, you can real quick see where any more problems are coming from and rule out what you did as a cause.