As JoeTaxpayer says, there's a lot you can do with just the stock price.
Exploring that a bit:
Stock prices are a combination of market sentiment and company fundamentals. Options are just a layer on top of that. As such, options are mostly formulaic, which is why you have a hard time finding historical option data -- it's just not that "interesting", technically. "Mostly" because there are known issues with the assumptions the Black-Scholes formula makes. It's pretty good, and importantly, the market relies on it to determine fair option pricing.
Option prices are determined by:
Relationship of stock price to strike. Both distance and "moneyness".
Time to expiration.
Dividends. Since dividend payments reduce the intrinsic value of a company, the prospect of dividend payments during the life of a call option depresses the price of the option, as all else equal, without the payments, the stock would be more likely to end up in the money. Reverse the logic for puts.
Volatility.
Interest rates. But this effect is so tiny, it's safe to ignore.
#4, Volatility, is the biggie. Everything else is known. That's why option trading is often considered "volatility trading". There are many ways to skin this cat, but the result is that by using quoted historical values for the stock price, and the dividend payments, and if you like, interest rates, you can very closely determine what the price of the option would have been. "Very closely" depending on your volatility assumption.
You could calculate then-historical volatility for each time period, by figuring the average price swing (in either direction) for say the past year (year before the date in question, so you'd do this each day, walking forward).
Read up on it, and try various volatility approaches, and see if your results are within a reasonable range.
Re the Black-Scholes formula,
There's a free spreadsheet downloadable from http://optiontradingtips.com. You might find it useful to grab the concept for coding it up yourself. It's VBA, but you can certainly use that info to translate in your language of choice. Or, if you prefer to read Perl, CPAN has a good module, with full source, of course. I find this approach easier than reading a calculus formula, but I'm a better developer than math-geek :)