Complex coacervate core micelles (C3Ms) are formed by mixing aqueous solutions of a charged (bio)macromolecule with an oppositely charged-neutral hydrophilic diblock copolymer. The stability of these structures is dependent on the ionic strength of the solution; above a critical ionic strength, the micelles will completely disintegrate. This instability at high ionic strengths is the main drawback for their application in, e.g., drug delivery systems or protein protection. In addition, the stability of C3Ms composed of weak polyelectrolytes is pH-dependent as well. The aim of this study is to assess the effectiveness of covalent crosslinking of the complex coacervate core to improve the stability of C3Ms. We studied the formation of C3Ms using a quaternized and amine-functionalized cationic-neutral diblock copolymer, poly(2-vinylpyridine)-block-poly(ethylene oxide) (QP2VP-b-PEO), and an anionic homopolymer, poly(acrylic acid) (PAA). Two different core-crosslinking strategies were employed that resulted in crosslinks between both types of polyelectrolyte chains in the core (i.e., between QP2VP and PAA) or in crosslinks between polyelectrolyte chains of the same type only (i.e., QP2VP). For these two strategies we used the crosslinkers 1-ethyl-3-(3′-dimethylaminopropyl)carbodiimide hydrochloride (EDC) and dimethyl-3,3′-dithiopropionimidate dihydrochloride (DTBP), respectively. EDC provides permanent crosslinks, while DTBP crosslinks can be broken by a reducing agent. Dynamic light scattering showed that both approaches significantly improved the stability of C3Ms against salt and pH changes. Furthermore, reduction of the disulphide bridges in the DTBP core-crosslinked micelles largely restored the original salt-stability profile. Therefore, this feature provides an excellent starting point for the application of C3Ms in controlled release formulations.