Los Maine Coons, como los American Shorthairs, se consideran nativos de América porque han estado en este continente desde los días coloniales, y quizás más tiempo. Cómo llegaron aquí en primer lugar y de dónde vinieron sus progenitores, sin embargo, es una conjetura de cualquiera, ya que ninguno de los colonos locales pasó por aquí con sus teléfonos con cámara para grabar el evento.
Existen muchas historias imaginativas sobre el origen de la raza (algunas más creíbles que otras), pero la prueba contundente es tan esquiva como un gato a la hora del baño. Una historia alega que la raza es un híbrido mapache/gato doméstico, de ahí el nombre de Maine Coon. Aunque tanto los mapaches como los Maine Coon tienen colas exuberantes y largas y la tendencia a sumergir su comida en su agua potable, tal unión es biológicamente imposible. Otra anécdota, poco probable pero al menos posible, sostiene que el Maine Coon fue producido por los tristes gatos domésticos/bobinos, lo que explicaría los mechones de orejas y dedos y el impresionante tamaño de la raza. Una historia más imaginativa afirma que los Maine Coon son descendientes de los gatos de pelo largo de María Antonieta. Los gatos y otras pertenencias de la Reina fueron contrabandeados a América por un capitán llamado Clough, que se preparaba para rescatar a la Reina de su encuentro con la guillotina. Desafortunadamente, la Reina perdió la cabeza, y los gatos terminaron quedándose con Clough en Maine. Por último, pero no menos importante, es la historia de un capitán de mar llamado Coon que, en la década de 1700, trajo gatos de pelo largo en sus excursiones a la costa noreste de América. Supuestamente, estos bucaneros de pelo largo se mezclaron con la población local mientras estaban de permiso en tierra.
Esta última historia tiene al menos un toque de verdad. Los marinos que usaban gatos para controlar las poblaciones de roedores en sus barcos de vela probablemente trajeron algunos gatos de pelo largo con ellos al Nuevo Mundo. Algunos de los gatos desembarcaron cuando llegaron a la costa noreste y se establecieron en las granjas y en los graneros de los primeros colonos. Dada la severidad del clima de Maine, esos primeros años debieron ser duros tanto para los gatos como para los humanos. Sólo sobrevivieron los más fuertes y adaptables de la raza. A través de la selección natural, el Maine Coon se convirtió en un gato grande y robusto con un pelaje denso y resistente al agua y una constitución robusta.
Independientemente de la procedencia de la raza, el Maine Coon fue una de las primeras razas en ser reconocida por la fantasía felina de finales del siglo XIX, y se convirtió en uno de los primeros favoritos. Sin embargo, a principios del siglo XX, a medida que se introducían nuevas y más exóticas razas en el país, los Maine Coon fueron abandonados por los Persas, Angoras y otros. Para 1950, la raza casi había desaparecido y de hecho fue declarada extinta en la década de 1950.
Afortunadamente, el anuncio de la desaparición del Maine Coon fue muy exagerado, y hoy en día estos gatos han recuperado su antigua gloria, sólo superados por el Persa en popularidad.