Political scientists lack a generally accepted definition of bargaining complexity, and attempts to quantify the complexity of political negotiations as such are rare. We argue that bargaining complexity is best defined as the amount of choice facing the negotiating actors, and best operationalized as the entropy of the probability distribution across potential bargaining outcomes. We apply this general approach to 343 government formation processes in advanced democracies, predicting the selection probability of each potential government using a state-of-the-art government formation model that integrates both arithmetic factors based on the number and size of parties and interparty relations, such as ideological dispersion and pre-electoral coalitions. We then demonstrate how to use our measure to disentangle between different determinants of bargaining complexity. Lastly, we show that bargaining complexity is robustly related to how many potential governments and partners were considered but ultimately set aside during negotiations and to the resulting cabinet’s durability.