We investigate the complexity of halfspace range searching: Given n points in d-space, build a data structure that allows us to determine efficiently how many points lie in a query halfspace. We establish a tradeoff between the storage m and the worst-case query time t in the Fredman/Yao arithmetic model of computation. We show that t must be at least on the order of (n/log n)1-(d-1)/d(d+1) /m1/d To our knowledge, this is the first nontrivial lower bound for halfspace range searching. Although the bound is unlikely to be optimal, it falls reasonably close to the recent O(n(log m/n)d+1/m1/d upper bound established by Matousek. We also show that it is possible to devise a sequence of n inserts and halfspace range queries that require a total time of n2-Θ(1/d). Our results imply nontrivial lower bounds for spherical range searching in any fixed dimension. For example they show that, with linear storage, circular range queries in the plane require Ω(n1/3) time (modulo a logarithmic factor).