For certain classes of negative definite symbols q(x,?) and state space dependent Bernstein function f(x,s) we prove that -p(x,D), the pseudo-differential operator with symbol -p(x,?) = -f(x,q(x,?)), extends to the generator of a Feller semigroup. Our result extends previously known results related to operators of variable (fractional) order of differentiation, or variable order fractional powers. New concrete examples are given.