We generalize the method of simultaneous linear estimation of multiple view geometry and lens distortion, introduced by Fitzgibbon at CVPR 2001 [6], to an omnidirectional (angle of view larger than 180?) camera. The perspective camera is replaced by a linear camera with a spherical retina and a non-linear mapping of the sphere into the image plane. Unlike the previous distortion-based models, the new camera model is capable to describe a camera with an angle of view larger than 180? at the cost of introducing only one extra parameter. A suitable linearization of the camera model and of the epipolar constraint is developed in order to arrive at a Quadratic Eigenvalue Problem for which efficient algorithms are known. The lens calibration is done from automatically established image correspondences only. Besides rigidity, no assumptions about the scene are made (e.g. presence of a calibration object). We demonstrate the method in experiments with Nikon FC-E8 fish-eye converter for COOLPIX digital camera. In practical situations, the proposed method allows to incorporate the new omnidirectional camera model into RANSAC - a robust estimation technique.