První vydání katalogu (1771)
Prvním objektem zapsaným v katalogu je Krabí mlhovina (M1), kterou Messier nalezl 28. srpna 1758 během hledání Halleyovy komety při jejím prvním předpovězeném návratu. Messier si nejprve myslel, že objevil další kometu, ale během několika dní zjistil, že se mlhovina nepohybuje, a tak změřil její souřadnice a vyznačil ji na mapě dráhy komety De la Nux (C/1758 K1).[3] Objev této mlhoviny Messiera přiměl k soustavnému hledání nových komet pomocí dalekohledu a přivedl ho k myšlence vytvoření seznamu objektů, které by mohly zmást i ostatní astronomy při hledání komet.
11. září 1760 Messier nalezl druhý nepohyblivý objekt, který později získal označení M2. Ještě i třetí objekt Messier nalezl spíše náhodou při hledání komet. Tímto objektem byla hvězdokupa M3, kterou objevil 3. května 1764. Teprve M3 byla prvním vlastním Messierovým objevem, protože Krabí mlhovinu jako první objevil John Bevis v roce 1731 a hvězdokupu M2 Giovanni Domenico Maraldi 11. září 1746. Zároveň hvězdokupa M3 označuje začátek období soustavného hledání mlhavých objektů, protože do konce roku 1764 Messier zapsal do katalogu i další objekty až po M40 a u 19 z nich je Messier považován za objevitele. Při tomto hledání používal i dostupné dřívější katalogy, z nichž některé jsou zmíněny výše, a dopisoval si s dalšími astronomy a vědci.
V roce 1765 pak nalezl hvězdokupu M41, ale tu znal i Giovanni Battista Hodierna před rokem 1654 a možná i Aristotelés. Na začátku roku 1769 se Messier zřejmě rozhodl, že svůj katalog zveřejní a přidáním čtyř dobře známých objektů M42 až M45 (Mlhovina v Orionu, hvězdokupa Jesličky a Plejády) vzrostl počet jeho položek na 45. První vydání svého díla představil 16. ledna 1771 Francouzské akademii věd v Paříži.