For most optimisation methods an essential assumption is the vector space structure of the feasible set. This condition is not fulfilled if we consider optimisation problems over the sphere. We present an algorithm for solving a special global problem over the sphere, namely the determination of Frechet means, which are points minimising the mean distance to a given set of points. The Branch and Bound method derived needs no further assumptions on the input data, but is able to cope with this objective function which is neither convex nor differentiable. The algorithm’s performance is tested on simulated and real data.