No, not all women bleed the first time. The reason that many bleed the first time is that the hymen tears. The hymen is a soft edge protruding from the wall of the vagina that makes it a bit narrow. When the penis penetrates for the first time, the hymen can tear resulting in a small amount of bleeding. This is completely normal. If you don’t bleed, it doesn’t mean that you don’t have a hymen, it just means that it isn’t attached to your vaginal wall. All women’s bodies are slightly different.