We construct composite and partially composite Higgs models with complex pseudo-Nambu-Goldstone (pNGB) dark matter states from four-dimensional gauge-Yukawa theories with strongly interacting fermions. The fermions are partially gauged under the electroweak symmetry, and the dynamical electroweak symmetry breaking sector is minimal. The pNGB dark matter particle is stable due to a U(1) technibaryon-like symmetry, also present in the technicolor limit of the models. However, the relic density is particle anti-particle symmetric and due to thermal freeze-out as opposed to the technicolor limit where it is typically due to an asymmetry. The pNGB Higgs is composite or partially composite depending on the origin of the Standard Model fermion masses, which impacts the dark matter phenomenology. We illustrate the important features with a model example invariant under an SU(4) × SU(2) × U(1) global symmetry.