We present a new approach to bounding financial derivative prices in regime-switching market models from both above and below. We derive sufficient conditions under which a particular class of functions act as bounds for the prices of financial derivatives in regime-switching market models. Using these sufficient conditions, we then formulate, in a general setting, optimization problems whose solutions can be identified with tight upper and lower bounds. The problems are made numerically tractable by imposing polynomial structures and employing results from the theory of sum-of-squares polynomials to arrive at a semidefinite programming problem that is implementable by existing software. The bounds obtained take the form of smooth polynomial functions and are valid for a continuous range of initial times and states. Moreover, they are obtained without recourse to sample path simulation or discretization of the temporal or spatial variables. We demonstrate the effectiveness of the proposed method on European-, barrier- and American-style options in several regime-switching settings with and without jumps.