Divalent-cation-based batteries are being considered as potential high energy density storage devices. The optimization of electrolytes for these technologies is, however, still largely lacking. Recent demonstration of the feasibility of Ca and Mg plating and stripping in the presence of a passivation layer or an artificial interphase has paved the way for more diverse electrolyte formulations. Here, we exhaustively evaluate several Ca-based electrolytes with different salts, solvents, and concentrations, via measuring physicochemical properties and using vibrational spectroscopy. Some comparisons with Mg- and Li-based electrolytes are made to highlight the unique properties of the Ca2+ cation. The Ca-salt solubility is found to be a major issue, calling for development of new highly dissociative salts. Nonetheless, reasonable salt solubility and dissociation are achieved using bis(trifluoromethanesulfonyl)imide (TFSI), BF4, and triflate anion based electrolytes and high-permittivity solvents, such as ethylene carbonate (EC), propylene carbonate (PC), γ-butyrolactone (gBL), and N,N-dimethylformamide (DMF). The local Ca2+ coordination is concentration-dependent and rather complex, possibly involving bidentate coordination and participation of the nitrogen atom of DMF. The ionicity and the degree of ion-pair formation are both investigated and found to be strongly dependent on the nature of the cation, solvent donicity, and salt concentration. The large ion-ion interaction energies of the contact ion pairs, confirmed by density functional theory (DFT) calculations, are expected to play a major role in the interfacial processes, and thus, we here provide electrolyte design strategies to engineer the cation solvation and possibly improve the power performance of divalent battery systems.