O regime de Capitanias Hereditárias foi instituído por D. João III em 1534. O fidalgo Duarte Coelho Pereira, donatário da capitania de Pernambuco, tomou posse de suas terras em 09 de março de 1535 quando desembarcou no porto de Itamaracá com sua família e parentes próximos. Em seguida, estabeleceu-se em um forte de madeira, na feitoria que fora fundada por Cristóvão Jaques em 1516, entre Pernambuco e Itamaracá. Pouco tempo depois ele seguiu para o sul em busca de um lugar para se instalar. Encontrou um local em situação estratégica, no alto de colinas, onde existia uma aldeia indígena denominada Marim, onde instalou o povoado que deu origem a Olinda, após uma série de conflitos com os antigos moradores, os caetés (ou tabajaras, segundo alguns autores), que foram vencidos, apesar de terem oferecido grande resistência ao invasor.

O local era tão aprazível, e com uma paisagem tão bela, que, segundo a tradição, o nome foi dado a partir de uma frase que teria sido dita por Duarte Coelho: “Oh! Linda situação para se construir uma vila”. Frei Vicente do Salvador, entretanto, em sua pioneira “História do Brasil” (de 1627, publicada em 1888), menciona essa versão atribuindo a frase a “um galego, criado de Duarte Coelho”. O povoado cresceu tanto que, em 1537, por Alvará do rei D. João III, foi elevado à categoria de vila e freguesia.

Em 12 de março desse mesmo ano Duarte Coelho firmou e enviou ao rei o Foral de Olinda, carta de doação na qual estabelecia o patrimônio público da vila, onde descrevia todos os lugares e benfeitorias ali existentes. Assim, a data oficial considerada como de sua fundação é 12 de março de 1537. A Câmara foi instalada na mesma data e, ainda no mesmo ano, Duarte Coelho ordenou a construção de um edifício destinado ao funcionamento do Senado da Câmara de Olinda. Nas praias a vila foi fortificada para a defesa e, do alto das colinas, se expandiu em direção ao mar, ao porto e ao interior onde ficavam os engenhos de açúcar.

Com a chegada das primeiras ordens religiosas – carmelitas (1580), jesuítas (1583), franciscanos (1585) e beneditinos (1586), foi feita a catequese dos índios, de fundamental importância para a consolidação da conquista das terras. Com o extrativismo do pau-brasil e o desenvolvimento da cultura da cana-de-açúcar, Olinda tornou-se um dos mais importantes centros comerciais da colônia, enriquecendo de tal maneira que disputava com a Corte portuguesa em luxo e ostentação. Foi a primeira capital de Pernambuco.

Em 1630 Olinda foi tomada pelos holandeses que a incendiaram em 24 de novembro de 1631, após saquearem os materiais nobres das edificações para construir suas casas no Recife, que começa a prosperar sob a administração holandesa. Por decisão do conde João Maurício de Nassau e do Alto Conselho, em 14 de novembro de 1639 foi transferida a Câmara de Escabinos de Olinda para a Ilha de Antônio Vaz (atual bairro de Santo Antônio, no Recife), perdendo Olinda a condição de capital de Pernambuco. Em 1654, novamente sob o domínio português, voltou a ser a sede oficial do governo, embora os governadores residissem no Recife.

Em 16 de novembro de 1676 um diploma pontifício do papa Inocêncio XI criou o Bispado de Olinda e lhe conferiu foros de cidade, ocasião em que a igreja da Sé (de São Salvador do Mundo) tornou-se catedral. O edifício do Senado da Câmara foi doado ao primeiro bispo de Olinda, D. Estevam Brioso de Oliveira, que o converteu em palácio episcopal. Em 14 de julho de 1678, através de Provisão Régia, foi confirmada a criação da vila.

Outro fato histórico de grande destaque foi o movimento precursor da república, ensaiado em 10 de novembro de 1710 no Senado da Câmara de Olinda, liderado pelo sargento-mor Bernardo Vieira de Melo, que deu o primeiro grito de república no Brasil, em prol da independência nacional. Em 29 de janeiro de 1787 um Alvará criou o distrito de Olinda.

Em 30 de maio de 1815, através de Alvará Régio, foi criada a comarca e Ouvidoria Geral da cidade de Olinda, pertencendo a ela os termos de Igarassu, Itamaracá, Goiana e Paudalho. Olinda foi a capital da província até o dia 15 de fevereiro de 1827, quando, por ordem de Sua Majestade Imperial, o Conselho do Governo decidiu pela transferência da capital para a cidade do Recife. Um Decreto Imperial de 11 de agosto de 1827 criou os dois primeiros Cursos de Ciências Jurídicas e Sociais do Brasil, um em São Paulo e o outro em Olinda, o qual foi solenemente instalado no Mosteiro de São Bento, a 15 de maio de 1828. Antes de sua transferência para o Recife, funcionaram no prédio em que atualmente se encontra a Prefeitura.

O distrito eleitoral foi criado em 15 de setembro de 1828, por resolução do Conselho do Governo de Pernambuco, ocasião em que a cidade de Olinda passou a ser uma das cabeças de distrito da província. Em 20 de maio de 1833, também por resolução do Conselho do Governo de Pernambuco (datada de 11 de maio), a comarca de Olinda foi extinta, passando a termo da então criada comarca de Santo Antônio do Recife, juntamente com os termos de Recife, Cabo, Igarassu e Itamaracá. A Lei Provincial nº 520, de 13 de maio de 1862, restaurou a comarca de Olinda, desmembrada da comarca de Recife, incluindo o termo de Igarassu (exIguarassu).

O distrito de Paulista foi criado e anexado ao município de Olinda pela Lei Municipal nº 219, de 28 de dezembro de 1907, e o distrito de Beberibe, pela Lei Municipal nº 231, de 02 de junho de 1908. Em 05 de dezembro de 1910 o Bispado de Olinda recebeu o predicamento de Arcebispado. Em divisão administrativa referente ao ano de 1911, o município é constituído de três distritos: Olinda, Paulista e Beberibe. A Lei Municipal nº 486, de 14 de novembro de 1922, criou em Olinda os distritos de Caboatam, Canoas, Jardim, Nobre e Praia da Conceição.

A Lei Estadual nº 1.931, de 11 de setembro de 1928, desmembrou de Olinda o distrito de Beberibe (anexado ao município do Recife) e o distrito de Paulista, que foi elevado à categoria de município. O município de Paulista foi extinto pelos decretos nº 268, de 25 de novembro de 1930, e nº 56, de 23 de janeiro de 1931, voltando à categoria de distrito de Olinda. A Lei Estadual nº 11, de 04 de setembro de 1935, restaurou o município de Paulista, desmembrando-o de Olinda. No quadro fixado para vigorar no período de 1944-48 o município é constituído apenas do distrito sede, assim permanecendo em divisão territorial datada de 1º de julho de 1960 e em divisão de 2005.

Por todo seu acervo histórico, arquitetônico e cultural, a Unesco reconheceu Olinda como Patrimônio Natural e Cultural da Humanidade , em 14 de dezembro de 1982.