Um den genauen Ursprung der Maine Coon ranken sich viele Legenden, wie z. B. die, daß ein »Captain Coon« auf seiner Reise nach Amerika einige Katzen auf seinem Schiff mitbrachte, die sich dann mit den einheimischen Katzen verpaarten. Eine andere besagt, daß Marie Antoinette noch vor ihrer Hinrichtung ihre Flucht aus Frankreich nach Amerika plante, und schon ihr Mobiliar und ihre Katzen vorausgeschickt habe. Nach einer weiteren (biologisch unmöglichen) Legende entstammt die Maine Coon der Verpaarung von Katze und Waschbär, was den schönen »Waschbärschwanz« erklären soll.

Die vermutlich dem wahren Ursprung am nächsten kommende Legende ist jedoch diese: die Katzen, die auf den Schiffen der Wikinger nach Amerika kamen, verpaarten sich mit den einheimischen Katzen und paßten sich den harten klimatischen Bedingungen an. Tatsächlich sehen die Norwegischen Waldkatzen den Maine Coons sehr ähnlich.

Anfangs wurden die in der Wildnis lebenden Katzen als gute Mäusefänger von den Farmern der Neuendland-Staaten hoch geschätzt. Später begann man mit einigen von ihnen zu züchten, um die Rasse zu festigen. 1895 gewann erstmals auf einer amerikanischen Katzenausstellung eine Maine Coon den Titel »Best in Show«, eine brown-tabby Maine Coon namens »Cosie« von Mrs. Francis R. Pierce.

Zwischenzeitlich verlor die Maine Coon durch die Beliebtheit der Perserkatzen noch einmal an Popularität. 1968 wurde die MCBFA gegründet, sie setzte sich für die Wiederanerkennung der Maine Coon als eigenständige Rasse ein. 1976 wurde die Maine Coon auch von der CFA anerkannt, erst seit 1983 von der FIFe.