En [[1534]], la tiama hereda privata provinco [[Pernambuko]] estis donita al [[Duarte COELHOCoelho]], kiu ekposedis ĝin en la [[9-a de marto]] [[1535]]. Li trovis lokon por fari militkonstruaĵon super montetoj kie estis malgranda indiĝena vilaĝeto Marim. Tiu loko estis tiel bela ke [[Duarte COELHOCoelho]] dirus: "Ó linda situação para se construir uma vila" (Ho belega loko por esti vilaĝo). En [[1630]], nerdelandanoj konkeris [[Pernambuko]]n kaj disrabis Olinda'n, kiu restis senhomoj ĝis [[1654]], kiam portugalanoj rekonkeris [[Pernambuko]]n, sed Olinda restis de tiam ĝis nun preskaŭ kvartalo de [[Recifo]].
