A esquadra partiu no dia seguinte, em meio às aclamações do povo que afluiu em massa para contemplar  o espetáculo. Na manhã do dia 14 navegavam entre as Canárias. No dia 22, ainda em março atravessaram o arquipélago de Cabo Verde. Na noite seguinte, desgarrou-se da frota a embarcação de Vasco de Ataíde. Tudo foi feito para encontrar o navio perdido. Em vão: a nau fora engolida pelas águas. Desfalcados, velejaram para oeste, até que no dia 21 de abril de 1500, terça- feira da Páscoa, reconheceram sinais de terra próxima. No dia seguinte, pela manhã, descortinaram um monte e um negrume prolongado no horizonte, sinal indicativo da continuação da linha litorânea. Cabral deu ao monte o nome de Pascoal, e à terra a denominação de ilha de Vera Cruz. No dia 23, navegaram  para terra firme, ancorando em frente a um rio, onde seriam travados os primeiros contatos com os indígenas. No dia seguinte, sexta-feira, rumaram para o norte. Os navios maiores fundearam ao largo, os de menor porte entraram num abrigo, no qual a armada inteira penetraria. Na manhã seguinte, domingo de Pascoela, armou-se um altar, onde o frei Henrique de Coimbra celebrou a primeira missa no Brasil. Foi cantada e assistida pelos sacerdotes da expedição, pelos capitães e marinheiros.

Os indígenas, atraídos pela novidade, acompanharam o ritual, imitando os gestos dos cristãos, Finalmente, a 02 de maio, Cabral zarparia de Porto Seguro em direção à Índia, com a missão de dar continuidade à rota aberta por Vasco da Gama. O Brasil  estava, assim, descoberto.