In this paper we develop a {\em primal-dual} subgradient method for solving huge-scale Linear Conic Optimization Problems. Our main assumption is that the primal cone is formed as a direct product of many small-dimensional convex cones, and that the matrix $A$ of corresponding linear operator is {\em uniformly sparse}. In this case, our method can approximate the primal-dual optimal solution with accuracy $\epsilon$ in $O\left({1 \over \epsilon^2}\right)$ iterations. At the same time, complexity of each iteration of this scheme does not exceed $O(r q \log_2 n)$ operations, where $r$ and $q$ are the maximal numbers of nonzero elements in the rows and columns of matrix $A$, and $n$ is the number variables.