In his textbook, Thermodynamics and an Introduction to Thermostatistics, H. B. Callen introduces entropy by the following four postulates:
Postulate I. There exist particular states (called equilibrium states) of simple systems that, macroscopically, are characterized completely by the internal energy $U$, the volume $V$, and the mole numbers $N_1, N_2, \dotsc, N_r$ of the chemical components.
Postulate II. There exists a function (called the entropy $S$) of the extensive parameters of any composite system, defined for all equilibrium states and having the following property: The values assumed by the extensive parameters in the absence of an internal constraint are those that maximize the entropy over the manifold of constrained equilibrium states.
Postulate III. The entropy of a composite system is additive over the constituent subsystems. The entropy is continuous and differentiable and is a monotonically increasing function of the energy.
Postulate IV. The entropy of any system vanishes in the state for which $$(\partial U/\partial S)_{V,N_1,\dotsc,N_r} = 0 \quad \textit{(that is, at the zero of temperature)}$$
From Postulate III follows that $S$ is homogeneous first-order, that $(\partial S/\partial U)_{V,N_1,\dotsc, N_r} > 0$ (hence $T \ge 0$), and that $U$ is a single-valued, continuous, and differentiable function of $S, V, N_1, \dotsc, N_r$. Postulate IV implies that $S$ has a uniquely defined zero. (This does not mean that there is a unique zero-entropy equilibrium state, but that, unlike $U$, one cannot redefine $S$ by addition of a constant.)
Now, in the context of statistical mechanics $S$ is certainly a nonnegative function, but I wonder if $S \ge 0$ also follows directly from the above postulates?
I can see that if one also has that $S$ is a strictly concave function of $U$ then postulates III and IV would imply $S \ge 0$, but I don't see how such concavity would follow from the postulates, so that might be a red herring.