We introduce the concept of a membership-concealing overlay network (MCON), which hides the real-world identities of participating nodes. We argue that while membership concealment is orthogonal to anonymity and censorship resistance, pseudonymous communication and censorship resistance become much easier if done over a membership-concealing network. We formalize the concept of membership concealment, discuss a number of attacks against existing systems and present real-world attack results. We then propose two proof-of-concept MCON designs that resist those attacks -- one that is more efficient, and another that is more robust to membership churn. We show theoretical and simulation results demonstrating the feasibility and performance of both schemes.