We present a tensor-network formulation for the strong-coupling expansion of QCD with staggered quarks at nonzero chemical potential, for arbitrary number of dimensions, colors, and flavors. We integrate out the gauge and quark degrees of freedom and rewrite the partition function as the complete trace of a tensor network. This network consists of local tensors that contain a numerical and a Grassmann part. We truncate the initial tensor at a fixed order in the inverse coupling β and compute analytical results for the partition function, the free energy, and the chiral condensate on a 2 × 2 lattice up to order β4. In a follow-up paper we will introduce an enhanced tensor-network method, order-separated GHOTRG, to explicitly compute the expansion coefficients of the partition function for larger lattices. To demonstrate its potential, first results obtained with this new method are already presented here.