We address the problem of depth and ego-motion estimation from omnidirectional images. We propose a correspondence-free structure from motion problem for images mapped on the 2-sphere. A novel graph-based variational framework is proposed for depth estimation. The problem is cast into a TV-L1 optimization problem that is solved by fast graph-based optimization techniques. The ego-motion is then estimated directly from the depth information without computation of the optical flow. Both problems are addressed jointly in an iterative algorithm that alternates between depth and ego-motion estimation for fast computation of the 3D information. Experimental results demonstrate the effective performance of the proposed algorithm for 3D reconstruction from synthetic and natural omnidirectional images.