Fondée en 1999 par Françoise Dugré et Alain Dion, Paraloeil a débuté avec des projets de diffusion avant de rapidement s’élargir vers la mise en place d’un centre d’accès en cinéma, incluant du soutien à la production, des ateliers pratiques et des formations.
En 2002-2003, grâce à l’offre de son propriétaire, M. Pearson, Paraloeil acquiert l’ancien cinéma l’Audito de Rimouski (originellement un théâtre fondé en 1946 et converti en cinéma), situé en plein cœur du quartier Saint-Robert, préservant sa réputation de véritable cinéma de quartier.
C’est en 2004 que Claude Fortin prend la direction générale de l’organisme, entamant une période de croissance. En 2005, Claude Forget (Vidéographe, Main Film, Cinéma libre) prend quant à lui la direction de la programmation. Dès lors, 75 projections sont organisées et le nombre d’entrées augmente de 50%. Parallèlement, une vingtaine de projets sont soutenus en production, et c’est le début des formations professionnelles.