We construct elliptic elements in the algebra of (classical pseudo-differential) operators on a manifold M with conical singularities. The ellipticity of any such operator A refers to a pair of principal symbols (σ0, σ1) where σ0 is the standard (degenerate) homogeneous principal symbol, and σ1 is the so-called conormal symbol, depending on the complex Mellin covariable z. The conormal symbol, responsible for the conical singularity, is operator-valued and acts in Sobolev spaces on the base X of the cone. The σ1-ellipticity is a bijectivity condition for all z of real part (n + 1)/2 − γ, n = dimX, for some weight γ. In general, we have to rule out a discrete set of exceptional weights that depends on A. We show that for every operator A which is elliptic with respect to σ0, and for any real weight γ there is a smoothing Mellin operator F in the cone algebra such that A + F is elliptic including σ1. Moreover, we apply the results to ellipticity and index of (operator-valued) edge symbols from the calculus on manifolds with edges.