In the era of high precision CMB measurements, systematic effects are beginning to limit the ability to extract subtler cosmological information. The non-circularity of the experimental beam has become progressively important as CMB experiments strive to attain higher angular resolution and sensitivity. The effect of non-circular beam on the power spectrum is important at multipoles larger than the beam-width. For recent experiments with high angular resolution, optimal methods of power spectrum estimation are computationally prohibitive and sub-optimal approaches, such as the Pseudo-C, method are used. We provide an analytic framework for correcting the power spectrum for the effect of beam non-circularity and non-uniform sky coverage (including incomplete/masked sky maps). The approach is perturbative in the distortion of the beam from non-circularity allowing for rapid computations when the beam is mildly non-circular. We advocate that when the non-circular beams are important, it is computationally advantageous to employ 'soft' azimuthally apodized masks whose spherical harmonic transforms die down fast with m. (c) 2006 Elsevier B.V. All rights reserved.