We analyze models where agents search for partners to form relationships (employment, marriage, etc.), and may continue searching for different partners while matched. Matched agents are less inclined to search if their match yields more utility and if it is more stable. If one partner searches, the relationship is less stable, so the other is more inclined to search, potentially making instability a self-fulfilling prophecy. We show this can generate a multiplicity - indeed, a continuum - of steady state equilibria. In any equilibrium there tends to be too much turnover, unemployment, and inequality compared to the efficient outcome. A calibrated version of the model explains 1/2 to 2/3 of reported job-to-job transitions.