The order Procellariiformes comprises mainly oceanic species that are occasionally recorded from along the Brazilian coast. We presents the first records of Lugensa brevirostris (Lesson, 1831) (Kerguelen Petrel) and Phoebetria palpebrata (Forster, 1785) (Light-mantled Albatross) for the state of São Paulo, Brazil. Both species were recorded from the municipality of Ilha Comprida. Lugensa brevirostris was recorded on 25 May 2016 and P. palpebrata on 3 October 2016. Therefore, we add 2 important records to the Brazilian avifauna and suggest the inclusion of both species on the list of birds in São Paulo.