Olá Alessandra
Se o serviço foi prestado em Fortaleza/CE, a regra geral da Lei Complementar 116/2003 determina que o ISS é devido no município do estabelecimento do prestador, salvo exceções específicas (como construção civil, cessão de mão de obra, vigilância etc.). Portanto, o fato de a pessoa estar fisicamente em Natal/RN não altera a competência tributária.
A nota fiscal deve ser emitida no município competente para o ISS, que, na maioria dos casos, será Fortaleza. Para emitir nota fiscal avulsa, deve-se acessar o sistema da Prefeitura de Fortaleza, verificar se há enquadramento para NFS-e avulsa (normalmente para pessoa física ou prestador eventual sem inscrição municipal), informar os dados do prestador, do tomador, descrição detalhada do serviço e valor. É importante analisar possíveis retenções de ISS, INSS e IRRF, conforme o tipo de serviço e tomador.
Espero ter ajudado.