In this paper, we study a natural extension of Kontsevich's characteristic class construction for A∞- and L∞-algebras to the case of curved algebras. These define homology classes on a variant of his graph homology that allows vertices of valence at least 1. We compute this graph homology, which is governed by star-shaped graphs with odd-valence vertices. We also classify non-trivially curved cyclic A∞- and L∞- algebras over a field up to gauge equivalence, and show that these are essentially reduced to algebras of dimension at most 2 with only even-ary operations. We apply the reasoning to compute stability maps for the homology of Lie algebras of formal vector fields. Finally, we explain a generalization of these results to other types of algebras, using the language of operads. A key observation is that operads governing curved algebras are closely related to the Koszul dual of those governing unital algebras.