De Papegaai is een voormalige huiskerk die rond het midden van de negentiende eeuw vervangen is door een kerk in de stijl van de zogenaamde stukadoorsgotiek. De oorspronkelijke inventaris is grotendeels bewaard gebleven.
In 1672 werd het woonhuis De Papegaai aan de Kalverstraat als rooms-katholieke statie ingericht. Omstreeks 1710 werd het verbouwd tot een huiskerk met drie beuken en galerijen. De kosten van de verbouwing werden betaald door het R.C. Armenkantoor. De Amsterdamse geschiedschrijver Jan Wagenaar gaf in 1765 een beschrijving van het interieur van de kerk: “In de kerke, een fraai, hoog gebouw, zijn twee galerijen, de onderste rust op vier ronde kolommen. ’t Altaar is zeer wel geschikt. Op hetzelve, staat een zwaar vergulde en konstig gedreven Tabernakel. Men heeft in deeze kerke verscheiden fraaie schilderijen, ook eenige van De Wit en daaronder eene de krooning der Lieve Vrouw verbeeldende”.
Plattegrond met de verschillende fasen van De Papegaai (1710, 1848, 1899)
Toen het rooms-katholicisme in Nederland geleidelijk weer openlijk beleden mocht worden, kon de huiskerk in 1848 vervangen worden door een nieuw en volwaardig kerkgebouw, ontworpen door Gerrit Moele jr. (1796-1857). De kerk werd gewijd aan de Heilige Jozef maar bleef toch beter bekend onder de naam De Papegaai.
Aanvankelijk fungeerde De Papegaai als bijkerk van de Franse kerk aan de Nieuwezijds Voorburgwal die aan de Heilige Petrus en Paulus was gewijd. Toen de Franse kerk in 1911 werd opgeheven, kreeg
De Papegaai de status van parochiekerk, nu met de Heilige Petrus en Paulus als patroonheiligen.
De kerk lag aanvankelijk inpandig maar kreeg in 1899, door verlenging van het middenschip, een ingang direct aan de Kalverstraat. In 1908 volgde een verlenging van het koor die gepaard ging met de bouw van het dwarsschip, de sacristie en kapellen aan weerszijden van het koor. Op de ranke torenspits (zichtbaar vanaf de Postzegelmarkt op de Nieuwezijds Voorburgwal) werd het kruis geplaatst dat afkomstig was van de toen net gesloopte Nieuwezijds Kapel. De pastorie aan de Nieuwezijds Voorburgwal 293 dateert uit 1914. Het portaal en de vestibule met trappenhuis werden in 1931-1932 in art deco-stijl verbouwd.
De Papegaai behoort tot de eerste fase van de neogotiek in Nederland, de zogenaamde stukadoorsgotiek of ook wel Willem-II gotiek genoemd, naar de regeerperiode van koning Willem II (1840-1849). In die periode beperkte de belangstelling voor de gotische architectuur zich tot de vormentaal ervan. Het visuele effect was belangrijker dan de daarvoor gebruikte middelen. Omdat de gotische bouwstijl met behulp van veel pleisterwerk werd geïmiteerd, werd deze vorm van neogotiek bekend als stukadoorsgotiek. 
Ogenschijnlijk lijkt het interieur van de Papegaai op een traditionele gotische hallenkerk (een kerk met drie even hoge beuken), compleet met bundelpijlers, schalken, spitsbogen en kruisribgewelven met ster- en netgewelven in het transept en koor. Maar constructief stelde het allemaal niets voor. De gewelven zijn namelijk niet van steen, maar gestuukt en vormen slechts een sierplafond.
In het laatste kwart van de negentiende eeuw wijzigde de aard van de neogotiek. Toonaangevende architecten als P.J.H. Cuypers en A. Tepe verschoven de aandacht toen vooral naar het aspect van de constructieve logica die aan de gotische bouwstijl ten grondslag lag.
De smalle neogotische gevel aan de Kalverstraat correspondeert niet met de breedte van het kerkinterieur. In
nissen aan weerszijden van de ingang bevinden zich beelden van een papegaai en van de eerste patroonheilige van de kerk, de H. Jozef. De mozaïeken in het portaal, met onder andere een voorstelling van de boetvaardige zondares Maria Magdalena, werden in 1932 door A. Molkenboer (1872-1960) vervaardigd.
Het portiek en de vestibule vormen de overgang naar het drie beukige interieur met dwarsschip en vijfzijdig gesloten koor, geflankeerd door de Maria- en Jozefkapel. Rechts van de Jozefkapel bevindt zich een doopkapel. De galerijen in de zijbeuken herinneren nog aan de indeling van de voormalige huiskerk.
Twee gebrandschilderde ramen van de galerij rechts met de voorstelling van de “Bedevaart naar Lourdes’’ zijn afkomstig van de Heilige Catharinakerk aan het Singel (ter plekke van de huidige Universiteitsbibliotheek) die in 1933 gesloten werd. Oorspronkelijk vormden ze één raam, dat echter in twee delen naar De Papegaai werd overgebracht.
De koorramen werden in 1934 vervaardigd door de glazenier Joep Nicolas (1897-1972), het grote raam in het rechter dwarsschip “Gaat en onderwijst alle volken’’ (1949) is van de hand van Pieter van Velzen (1911-1990).
De inventarisstukken zijn nog voor een groot deel oorspronkelijk en vormen een integraal onderdeel van de architectuur. De verschillende interieuronderdelen sluiten op elkaar aan dankzij het consequente gebruik van eikenhout en door de steeds terugkerende gotische sierelementen als drie- en vierpasvormen, kruisbloemen, pinakels en spitsbogen.
Enkele belangrijke interieuronderdelen zijn:
Het hoogaltaar uit 1850, vervaardigd in het atelier van Louis Veeneman (1812-1888) in Den Bosch. De reliëfs dateren uit 1909 en beelden het offer van Melchisedek en de Wonderbare broodvermenigvuldiging uit.
De rijk gebeeldhouwde zeshoekige preekstoel met torenbaldakijn, eveneens van Veeneman; De altaren in de Jozef- en Mariakapel uit het meubelatelier Jansen & Zonen. Een aantal heiligenbeelden (een zittende en een staande Heilige Maria, een beeld van H. Jozef) afkomstig uit het atelier van P.J.H. Cuypers en Stoltenberg in Roermond.
De twee barokke marmeren engelenbeelden in de doopkapel door de Antwerpse beeldhouwer Michiel van der Voort (1667-1737) die afkomstig zijn van de Franse kerk. Van dezelfde beeldhouwer bevinden zich in het Museum Amstelkring, “Ons Lieve Heer op Solder”, de marmeren beelden van de patroonheiligen van de Franse kerk, en nu van De Papegaai, de Heilige Petrus en Paulus.
De veertien schilderijen van de Kruisweg in de neogotische omlijsting langs de zijwanden zijn van de hand van C.F. Philippeau (1825-1897). Bij funderingsherstel uitgevoerd in 2004 kwamen bouwsporen van de vroeg-achttiende-eeuwse huiskerk aan het licht. Daaruit blijkt dat de oude kerk vijftien meter lang en 8,5 meter breed was, met galerijen van ongeveer 1,60 m breedte. Van de vier ronde kolommen waarover Wagenaar sprak, werden de vierkante blokken (poeren) gevonden waarop de basementen van de kolommen rustten. Ze waren onderling verbonden door gemetselde spaarbogen. Uit de plaatsing van de kolommen bleek dat de middenas van de achttiende-eeuwse kerk iets verschoven lag ten opzichte van de huidige situatie.