In 1598 , the Portuguese built the Forte dos Reis Magos . The next year , they created the city of Natal . In 1598 , the Portuguese built the Forte dos Reis Magos and , in the following year , founded the city of Natal .