De historische oorsprong van de Orde is enigszins onduidelijk, hoewel volgens een niet-gedocumenteerde traditie deze wordt teruggevoerd tot de Eerste Kruistocht. Sterker nog, het eerste documentaire bewijs van een investituur van Ridders die "van het Heilig Graf" wordt genoemd, dateert van 1336. Sinds dit eerste getuigenis van het bestaan van de Orde, dat wil zeggen vanaf de XIVe eeuw, hebben de pausen geleidelijk en regelmatig hun wens uitgesproken om de organisatie juridisch te verbinden aan de Heilige Stoel.

De Ridderlijke Orde van het Heilig Graf van Jeruzalem heeft altijd geprofiteerd van de bescherming van de Pausen, die de Orde door de eeuwen heen hebben gereorganiseerd en haar voorrechten hebben uitgebreid en verrijkt. Clemens VI vertrouwde in 1342 de bewaring van het Heilig Graf toe aan de Franciscaner monniken, maar dat was nog in een tijdperk waarin alleen Ridders het recht hadden om andere leden van de Orde te creëren. Alexander VI verklaarde zichzelf in 1496 tot de hoogste moderator van de Orde, en delegeerde aan de Franciscanen de bevoegdheid om edelen en pelgrims die op bedevaart naar het Heilige Land gingen tot ridder te slaan (investituremacht). Bevestiging van dit Franciscaanse voorrecht, hetzij mondeling, hetzij per pauselijke Bul, werd vernieuwd door Paus Leo X in 1516, door Benedictus XIV in 1746, tot aan het herstel van het Latijnse Patriarchaat van Jeruzalem door Pius IX in 1847.

Zo werd de pauselijke delegatie overgedragen aan de Patriarch toen Pius IX in 1868 Apostolische brieven uitvaardigde waarin het herstel van de Orde werd aangekondigd. De Orde van Ridders opende zich met de benoeming van de Dames van het Heilig Graf dankzij Leo XIII, in 1888. Bovendien besloot Pius X in 1907 dat de titel van Grootmeester van de Orde voorbehouden zou zijn aan de Paus zelf.

In 1932 keurde Pius XI de nieuwe Constitutie goed en stond hij Ridders en Dames toe hun investiture te ontvangen in hun plaats van herkomst en niet alleen in Jeruzalem. In 1940 benoemde Pius XII een kardinaal tot Beschermheer van de Orde en centraliseerde hij de organisatie in Rome, als onderdeel van het Grootmagisterium, waarbij hij de titel van Grootmeester overdroeg aan Kardinaal Canali. Johannes XXIII keurde de nieuwe Constitutie goed, gepresenteerd door Kardinaal Tisserant in 1962.

Met de vernieuwing van het Tweede Vaticaans Concilie werd een nieuwe Constitutie goedgekeurd door Paulus VI in 1977. Vervolgens maakte Johannes Paulus II van de Orde een juridische canonieke en publieke persoonlijkheid, ingesteld door de Heilige Stoel. Vandaag streeft de Orde ernaar de betrokkenheid van haar leden in lokale kerken te bevorderen, in de hoop op hun heiliging. Dit is de essentiële en diepgaande reden die de herziening van de Constitutie tijdens de "Consulta" die in 2013 plaatsvond, heeft gemotiveerd.