Emissário português avistou a Ilha de São Vicente dois dias antes da fundação

Martim Afonso de Souza não veio diretamente para São Vicente. Em janeiro de 1531, ele chegou a Pernambuco e dali mandou um mensageiro voltar a Portugal levando notícias ao Rei, enquanto seguia para o Sul. Aportou na Bahia, onde se encontrou com Caramuru. De acordo com os registros, em 30 de abril de 1531 ele chegou à Baía da Guanabara, onde mandou construir uma casa forte e instalar uma pequena ferraria para reparo das naus.

Em 1º de agosto, a expedição continuou seu caminho, chegando em 12 de agosto à Baía de Cananéia, onde o navegador encontrou portugueses e espanhóis.Nessa viagem pela costa brasileira, durante quase um ano Martim Afonso enfrentou tempestades, assistiu ao naufrágio da nau Capitânia e participou de um combate a navios franceses que faziam contrabando de pau-brasil.

Em 20 de janeiro de 1532, a esquadra vê surgir a Ilha de São Vicente. Porém, o mau tempo impediu a entrada dos navios na barra e a descida à terra firme só aconteceu no dia 22 de janeiro. Coincidentemente, nesse mesmo dia, 30 anos antes, a expedição do também navegador português Gaspar Lemos havia chegado aqui e batizado o local como São Vicente, em homenagem a São Vicente Mártir. Martim Afonso, católico fervoroso, ratificou o nome.
Isso porque, logo após a sua chegada, ele adotou as medidas recomendadas pelo Rei de Portugal e organizou um sistema político-administrativo nas novas terras. Assim, após batizar o local oficialmente como Vila de São Vicente, Martim Afonso instalou aqui a Câmara, o Pelourinho, a Cadeia e a Igreja, símbolos da colonização e bases da administração portuguesa.

Para São Vicente, o título de Vila representava mais benefícios para o povo, já que esse era o termo utilizado pelos portugueses para designar uma cidade organizada. É desse fato que deriva o título vicentino de Cellula Mater da Nacionalidade, ou Primeira Cidade do Brasil.