The structure of small clusters of Bi2O3 on the (001) surface of SrTiO3 are examined using ab initio density functional theory. In these clusters the local Bi environments are highly distorted, resembling locally those in the ordered alpha and beta phases of Bi2O3, but on the surface arranged together in different ways as in the disordered delta phase. Thus we propose that the stabilization of the delta phase of Bi2O3 on this surface arises not from the epitaxial matching of Bi ... Bi with Sr ... Sr, but from mismatch between cluster Bi-O and surface Sr-O bond lengths. This gives rise to critical areas (i.e., maximum domain sizes) for individual Bi-O islands on the surface, thus promoting different arrangements of the Bi and the formation of a disordered surface phase. The formation of the film is associated with a considerable decrease in the band gap.