That is a very open ended question. In a general sense, yes a slightly taller building will require a slightly stronger foundation. But there are many considerations. Are you using shallow (bearing on soil) or deep foundations (piles/drill shafts)? Depending on where you are on earth, wind or earthquakes impart most of your lateral loading, which cause overturning moments and depending on how heavy (dead load) you structure is, it might either have selfweight to resist that, or require a foundation heavy enough, or for deep foundations piles with uplift capacity.
Also, just to be clear, I guess you are talking about an office of residental building when mentioning stories, realize some very large buildings are single story.
http://en.wikipedia.org/wiki/Vehicle_Assembly_Building
If, you are not concerned about any lateral loading causing overturning and it is a simple question of vertical loads. Then, for a shallow foundation, the depth probably would not vary, the size of the footing would. So you might be told the soil can support 1 tsf (ton per square foot), if your column load is 100 tons, then you'd need 100 sf. There are load factors, and reduction factors that would be applied as well depending on design codes that apply. If you are on a deep foundation, then in its case of how many piles and how deep, both of which will be site specific, and would determined by geotechnical investigation, typically through boring logs. A miniumum depth would be established, and normally capacity in piles increases with depth sometimes very quickly, 100 ton vs 120 ton might be a 50 ft pile vs 55 ft. There is no generalization however, this is entirely site specific, it might be 20 ft someplace and 250 ft somewhere else, soils vary.
http://en.wikipedia.org/wiki/Foundation_(engineering )